10816번: 숫자 카드 2
https://www.acmicpc.net/problem/10816
문제 정의
상근이는 숫자 카드 N개를 가지고 있다. 정수가 M개 주어졌을 때, 이 수가 적혀있는 숫자 카드를 상근이가 몇 개 가지고 있는지 구하면 된다.
만약 상근이가 6 3 2 10 10 10 -10 -10 7 3 카드를 가지고 있을 때,
10 9 -5 2 3 4 5 -10 → 이 숫자들을 몇개 씩 가지고 있는지 출력하면 된다.
이 예에서는 10은 3개 가지고 있으므로 3으로 출력하면 된다.
접근 방법
N과 M이 최대 500,000이 될 수 있는데, 일일히 2개의 리스트를 비교하기에는 으로 시간 초과가 뜰 수 있다.
그래서 x가 리스트 안에 몇 개 있는지 찾기 위해서 기준 숫자인 mid를 기준으로 이후/이전에서 찾는다면 훨씬 빨리 찾을 수 있을거라고 생각했다.
👉 이분 탐색으로 접근하자!
상근이가 가지고 있는 카드의 숫자가 각각 몇 번 등장하는지 저장하는 딕셔너리가 필요하다. → n_dic
이분 탐색을 사용해서 n_dic을 구하고 난 뒤,
찾아야 하는 숫자들이 몇 번 등장했는지를 n_dic에서 찾아 출력하면 된다.
(사실 처음에는 이분탐색 구현을 제대로 하지 못해서 시간초과가 났다.)
문제 해설
- 상근이가 가지고 있는 카드리스트에서 각 카드가 몇 번 등장하는지 세고 딕셔너리에 저장한다.
- 카드를 찾기 위해서, 상근이의 카드리스트를 이분 탐색한다.
- 이분 탐색을 하기 위해서는 상근이의 카드 리스트를 정렬 해야한다.
- 주어진 카드리스트를 확인하면서, 해당 숫자가 몇번 등장했는지 딕셔너리에서 찾아와 리턴해준다.
풀이
- 처음에 시도했던 풀이 → 시간 초과
- 단순히
mid를 구해서 한번만 반을 잘라서 찾았음. → 이분 탐색이 아니다!
import sys
input = sys.stdin.readline
N = int(input()) # 상근이가 가지고 있는 숫자 카드 개수
cards = list(map(int, input().split())) # 상근이가 가지고 있는 숫자 카드에 적혀있는 정수
M = int(input())
M_cards = list(map(int, input().split())) # 상근이가 몇개 가지고 있는지 요구되는 정수들
count = [] # 몇개 가지고 있는지 카운트 리스트
# 10 9 -5 -> 10 몇개? 9 몇개? -5 몇개?
# -10 -10 2 3 3 [6] 7 10 10 10
# 10이면 6보다 크므로 6이후에서 찾기
# 9면 6보다 크므로 6이후에서 찾기
cards.sort() # 오름차순으로 정렬
for c in M_cards:
cnt = 0 # 카드 몇 개인지 카운트
if c > cards[len(cards)//2]:
# 이후에서 찾기
cnt += cards[len(cards)//2:].count(c)
else:
# 이전에서 찾기
cnt += cards[:len(cards)//2].count(c)
count.append(cnt)
print(' '.join(list(map(str, count))))
- 이분 탐색을 활용한 올바른 풀이
- 이분 탐색을 하다가 해당 숫자를 찾았으면?
👉
array[start:end+1]중 찾고자 하는 숫자가 몇 개 인지 센다.
import sys
input = sys.stdin.readline
N = int(input()) # 상근이가 가지고 있는 숫자 카드 개수
cards = list(map(int, input().split())) # 상근이가 가지고 있는 숫자 카드에 적혀있는 정수
cards.sort() # 이분탐색을 위한 정렬!!!!
M = int(input())
M_cards = list(map(int, input().split())) # 상근이가 몇개 가지고 있는지 요구되는 정수들
def binary_search(array, target, start, end):
if start > end:
return 0
mid = (start + end) // 2
if array[mid] == target:
return array[start:end+1].count(target)
elif array[mid] < target:
return binary_search(array, target, mid+1, end)
else:
return binary_search(array, target, start, mid-1)
n_dic = {} #상근이가 가지고 있는 카드숫자가 몇 번 등장했는지 저장한 딕셔너리
for c in cards:
if c not in n_dic:
n_dic[c] = binary_search(cards, c, 0, N-1) # 여기서 이분탐색
for i in M_cards:
if i in n_dic:
print(n_dic[i], end = ' ')
else:
print(0, end = ' ')
꿀팁
- 파이썬의 Counter 라이브러리를 사용해서 등장 딕셔너리를 만들 수 있다.
from sys import stdin
from collections import Counter
_ = stdin.readline()
N = stdin.readline().split()
_ = stdin.readline()
M = stdin.readline().split()
C = Counter(N)
print(C)
>> # Counter({'10': 3, '3': 2, '-10': 2, '6': 1, '2': 1, '7': 1})
print(' '.join(f'{C[m]}' if m in C else '0' for m in M))정리
- 이분 탐색을 제대로 구현하지 못해서 풀지못한 문제이다.
- 이분탐색의 개념 공부를 다시 해야겠다…
Uploaded by N2T
