[BOJ] 10815. 숫자 카드(Python) / Binary Search

10815번: 숫자 카드

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

# 38분 소요

• 사용 알고리즘 : Binary Search(이분 탐색)
• 풀 수 있는 방법이 많겠지만, 이분 탐색에 취약한 나는 코드 연습 겸 이분 탐색으로 코드를 짰다.
• numLst, chkLst 각 리스트를 Input 받고 chkLst에 대해서는 숫자별 인덱스를 저장하는 딕셔너리를 만들었다.
• 두 리스트에 대해 정렬
• 이진 탐색으로 해당 숫자를 찾았다. 
• 숫자 일치할 때 0으로 초기화된 findLst의 해당 숫자의 인덱스(numInfo 딕셔너리 참조) 위치를 1로 바꿔준다.
• 형식에 맞게 출력한다. 

 

파이썬 코드는 다음과 같다.

---

from sys import stdin
input = stdin.readline

N = int(input())
numLst = list(map(int, input().split()))    # 상근이가 가진 숫자 리스트
M = int(input())
chkLst = list(map(int, input().split()))    # 체크해야 할 숫자 리스트
numInfo = {v: i for i, v in enumerate(chkLst)}	 # 원본 숫자별 인덱스 딕셔너리에 저장

numLst.sort()
chkLst.sort()

findLst = [0] * M     # 찾은 숫자 1로 표시

for i in range(M):
    num = chkLst[i]     # 찾을 숫자
    left, right = 0, N-1
    while left <= right:
        mid = (left+right) // 2
        if num < numLst[mid]:
            right = mid - 1
        elif num > numLst[mid]:
            left = mid + 1
        else:   # 숫자 일치
            findLst[numInfo[num]] = 1
            break
            
print(*findLst)

---

• 시간 : 816ms / 메모리 : 260624kb
• 고찰 : Set 등을 이용해 더 빨리 구할 수 있었지만, 이분 탐색으로 구현했다. 오히려 시간/공간 복잡도는 더 나왔지만 말이다 ㅋㅋㅋ 가장 기본적인 이분탐색 문제였다.