백준 10816번: 숫자 카드 2

문제

문제 바로가기> 백준 10816번: 숫자 카드 2

풀이

def binarySearch(x):
    low, high = 0, len(card)-1
    while low <= high:
        mid = (low+high)//2
        if x == card[mid]:
            return mid
        elif x < card[mid]:
            high=mid-1
        else:
            low=mid+1
    return -1

def lowerBound(x):
    low, high = 0, len(card)
    while low < high:
        mid = (low + high) // 2
        if x <= card[mid]:
            high = mid
        else:
            low = mid+1
    return low

def upperBound(x):
    low, high = 0, len(card)
    while low < high:
        mid = (low + high) // 2
        if x < card[mid]:
            high = mid
        else:
            low = mid + 1
    return low

N = int(input())
card = list(map(int, input().split()))
card.sort()
M = int(input())
sg_have = list(map(int, input().split()))
ans = list()

for i in sg_have:
    mid_idx = binarySearch(i)
    if mid_idx == -1:
        ans.append(0)
    else:
        if card[0]==card[mid_idx] and card[-1]==card[mid_idx]:
            ans.append(len(card))
        else:
            ans.append(upperBound(i)-lowerBound(i))
print(*ans)

처음에 시도한 방법은 이진탐색을 이용하여 푸는 것이었는데, 시간초과가 계속 발생하였다. (upper bound와 lower bound를 구하는 과정에서 시간이 오래 걸린 것이다.) pypy3로 실행하니 통과되기는 했지만, 그럼에도 많은 시간과 메모리를 잡아 먹었다.

pypy3는 자주 쓰이는 코드를 캐싱해서,
간단한 코드 상에서는 python3가 메모리, 속도면에서 유리하고
복잡한 코드(반복) 상에서는 pypy3가 낫다고 한다!

코드 개선

N = int(input())
card = list(map(int, input().split()))
M = int(input())
sg_have = list(map(int, input().split()))

card_count = dict()
for i in card:
    if i in card_count:
        card_count[i]+=1
    else:
        card_count[i]=1
for i in sg_have:
    if i in card_count:
        print(card_count[i], end=' ')
    else:
        print(0, end=' ')

다음으로 시도한 방법은 dictionary를 이용하는 방법이었다. 애초에 입력받은 list를 반복문을 돌면서 count하고 이 결과를 dictionary에 저장해주었다. 이 방법이 메모리, 속도, 구현 모든 측면에서 더 좋았다.
내가 초반에 너무 이진 탐색에만 몰두했던 것 같아서 아쉬웠고, 다양한 방법으로 문제에 접근해야겠다고 생각했다.