백준 알고리즘 10816번 숫자 카드 2(python)

10815번 숫자 카드 문제랑 비슷한데. 개수를 새야 한다는 점만 다르다.

이 문제는 이분 탐색 또는 딕셔너리를 사용해서 풀 수 있는데, 딕셔너리를 사용해서 푸는 게 효율적인 것 같다.

 

이분 탐색 풀이

1) 처음에 아래와 같이 풀어서 제출했었는데 시간 초과가 나왔었다.

많은 양의 값들을 리스트에 append 해서 시간이 오래 걸린 것 같다. 

def binarySearch(li, n):
    s, e = 0, len(li)-1
    while s <= e:
        m = (s + e) // 2 
        if li[m] == n:
            return li[s:e+1].count(n)
        if n > li[m]:
            s = m + 1
        else:
            e = m - 1
    return 0
    

N = int(input())
li1 = sorted(map(int, input().split()))
M = int(input())
li2 = list(map(int, input().split()))
result = []

for n in li2:
    result.append(binarySearch(li1, n))
print(*result)

2) 딕셔너리에 결괏값들을 저장했더니 해결되었다!

binarySearch 함수는 동일하다

N = int(input())
li1 = sorted(map(int, input().split()))
M = int(input())
li2 = list(map(int, input().split()))

d = {}
for n in li1:
    if n not in d:
        d[n] = binarySearch(li1, n)
        
print(' '.join(str(d[m]) if m in d else '0' for m in li2))

 

딕셔너리 풀이

압도적 성능을 자랑한다. 이분 탐색 풀이는 3000ms나 걸렸는데, 딕셔너리 풀이는 800ms 밖에 시간이 걸리지 않는다.

N = int(input())
li1 = list(map(int, input().split()))
M = int(input())
li2 = list(map(int, input().split()))
d = {}

for n in li1:
    d[n] = d.get(n, 0) + 1
print(' '.join(str(d[m]) if m in d else '0' for m in li2))

 

딕셔너리를 사용한게 압도적으로 빠름