백준 10815번(silver 5) : 숫자 카드 (딕셔너리, 이진탐색)

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

10815번: 숫자 카드

---

 

 내가 작성한 코드 - 시간초과 

import sys

input = sys.stdin.readline
# 상근이가 갖고 있는 카드의 개수와 카드에 적힌 숫자
n = int(input())
cards = list(map(int, input().split()))
# 비교군 카드
m = int(input())
compare = list(map(int, input().split()))
# 출력할 리스트
result = []

for i in range(m):
    if compare[i] in cards:
        result.append(1)
    else:
        result.append(0)

for i in result:
    print(i, end=" ")

 

찾아보니 리스트로 접근하는 것보다 딕셔너리로, 혹은 이진탐색을 이용하는 것이 시간 단축할 수 있다는 것을 알게 되었다.

---

 

 수정한 코드 - 딕셔너리 

import sys
input = sys.stdin.readline

# 상근이가 갖고 있는 카드의 개수와 카드에 적힌 숫자
n = int(input())
cards = list(map(int, input().split()))
# 비교군 카드
m = int(input())
compare = list(map(int, input().split()))

# 리스트를 딕셔너리로 변환
# 초기 value 값은 0으로
# compare 리스트의 요소와 일치하다면 1로 바꾸기

cards_dic = {}
for i in range(n):
    cards_dic[cards[i]] = 0

for j in range(m):
    if compare[j] in cards_dic :
        print(1, end=' ')
    else:
        print(0, end=' ')

 

 

 수정한 코드 - 이진탐색 

import sys
input = sys.stdin.readline

# 상근이가 갖고 있는 카드의 개수와 카드에 적힌 숫자
n = int(input())
cards = list(map(int, input().split()))
cards.sort()
# 비교군 카드
m = int(input())
compare = list(map(int, input().split()))

# 이진탐색
for com in compare:
    low, high = 0, n-1
    fin = False
    while low <= high:
        mid = (low+high) // 2
        if cards[mid] > com:
            high = mid - 1
        elif cards[mid] < com:
            low = mid + 1
        else:
            fin = True
            break
    print(1 if fin else 0, end= ' ')

---

 

 결과 

위에서부터 이진탐색, 딕셔너리, 내 정답(리스트)

 

당연히 이진탐색 알고리즘이 가장 빠를 줄 알았는데 딕셔너리로 작성한 코드가 훨씬 빨랐다. 딕셔너리가 이렇게까지 빠른 줄 몰랐다. 나중에 문제를 풀 때 딕셔너리를 자주 사용해야겠다.