[백준] 10815번: 이분탐색과 딕셔너리 - Python

https://www.acmicpc.net/problem/10815

 

위의 문제를 풀다가 

이것 저것 생각하다가 풀이를 2개를 작성했는데

간단하게 정리하려고 작성합니다.

두 가지 풀이를 했습니다.

문제를 먼저 보면, max(N)은 50만개, max(M)은 50만개라

O(N^2)으로 시간복잡도가 넘어가는 순간 2500억번의 계산을 해야합니다.

그러면 우리의 갓갓 PyPy3도 2초는 넘길 것 같습니다. 

(여기서는 O(N * M)이죠)

---

그래서 이 문제 풀이의 핵심은 이중 for문을 사용하지 말고

리스트 안에 들어있는 걸 확인해라!! 입니다.

---

그러면 다른 방법은 많지만 저는 보통 딕셔너리와 이중탐색을 떠올립니다. (정답이 아닐 수 있지만

뭐 제가 떠올리는 것들입니다.)

딕셔너리의 서치 속도는 O(1)이니, 없는 카드만 신경쓰면 될 것이고

이중탐색(바이너리 서치)은 O(LogN)이었던 것으로 기억을 해서 O(M * LogN)으로 O(N^2)은 피할 수 있겠군요.

속도는 당연히 딕셔너리가 빠릅니다. :)

---

딕셔너리 코드

import sys

n = int(sys.stdin.readline())
s_cards = list(map(int,sys.stdin.readline().split()))
dict_card = {}
for s_card in s_cards:
    dict_card[s_card] = 1

m = int(sys.stdin.readline())
cards = list(map(int,sys.stdin.readline().split()))

answer = []
for card in cards:
    try:
        answer.append(dict_card[card])
    except KeyError:
        answer.append(0)

print(*answer)

이중 탐색 코드

import sys


def binary_search(target, data):
    start = 0
    end = len(data) - 1

    while start <= end:
        mid = (start + end) // 2

        if data[mid] == target:
            return 1
        elif data[mid] > target:
            end = mid - 1
        else:
            start = mid + 1
    return 0


def solution(sae_cards, new_cards):
    result = []
    sae_cards.sort()
    for new_card in new_cards:
        result.append(binary_search(new_card, sae_cards))

    return result


n = int(sys.stdin.readline())
s_cards = list(map(int,sys.stdin.readline().split()))

m = int(sys.stdin.readline())
cards = list(map(int,sys.stdin.readline().split()))

print(*solution(s_cards, cards))

시간도 확인하시라고 가져왔습니당.

위 2개가 이중 탐색, 밑 2개가 딕셔너리