1. 문제
  2. 이분탐색을 이용한 풀이(시간초과)
  3. 딕셔너리를 이용한 풀이

문제

숫자 카드는 정수 하나가 적혀져 있는 카드이다. 상근이는 숫자 카드 N개를 가지고 있다. 정수 M개가 주어졌을 때, 이 수가 적혀있는 숫자 카드를 상근이가 몇 개 가지고 있는지 구하는 프로그램을 작성하시오.

이분탐색을 이용한 풀이(시간초과)

지금까지 배웠던 이분탐색으로 접근하면 숫자를 찾을수는 있어도 그 개수는 찾지 못한다. 각 정수마다 배열을 모두 훑으면서 개수를 찾으면 시간초과.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
이분탐색으로 접근 - 실패
deck.sort()
def find_card(n):
    start = 0
    end = N-1
    while start <= end :
        p = (start + end) // 2
        if deck[p] > n:
            end = p - 1
        elif deck[p] < n :
            start = p + 1
        elif deck[p] == n:
            cnt = 1
            i, j=1, 1
            while p-i>= 0:
                if deck[p-i] == n:
                    cnt += 1
                    i += 1
                else:
                    break
            while p+j < N:
                if deck[p+j] == n:
                    cnt += 1
                    j += 1
                else:
                    break
            return cnt
    return 0

answer = []
for i in range(M):
    answer.append(str(find_card(card[i])))

print(' '.join(answer))

딕셔너리를 이용한 풀이

숫자를 key로 가지는 딕셔너리를 활용한다면, 입력을 받음과 동시에 개수를 저장할 수 있다. 이 때의 복잡도는 O(n)으로 훨씬 빠르다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
import sys

N = int(sys.stdin.readline().strip())
deck = list(map(int, sys.stdin.readline().split()))
M = int(sys.stdin.readline().strip())
card = list(map(int, sys.stdin.readline().split()))

hash = {}
for i in deck:
    if i in hash:
        hash[i] += 1
    else:
        hash[i] = 1
answer = []
for i in card:
    if i in hash:
        answer.append(str(hash[i]))
    else:
        answer.append('0')
print(' '.join(answer))