(BOJ)-10815, Python

문제 요약

출처: (BOJ)10815 - 숫자 카드

상근이는 숫자 카드 $N$개를 가지고 있다. 주어진 $M$개의 숫자 카드에 대해, 각각의 카드가 상근이가 가진 카드인지 여부를 판별하는 문제이다.

두 숫자 카드에 같은 수가 적혀있는 경우는 없다. 숫자 카드를 상근이가 가지고 있으면 $1$을, 아니면 $0$을 공백으로 구분해 출력한다.

접근 과정

1. 완전탐색 접근(반복문)

주어진 숫자 카드마다 상근이가 가진 모든 카드를 탐색하도록 구현했지만, 결과는 시간 초과였다.

구현한 코드

N = int(input())
N_arr = list(map(int, input().split()))
M = int(input())
M_arr = list(map(int, input().split()))
answer = [0 for _ in range(M)]

for idx, M_num in enumerate(M_arr):
    for N_num in N_arr:
        if M_num == N_num:
            answer[idx] = 1
    
print(*answer)

2. 이분탐색 접근(투 포인터)

이분 탐색은 1부터 100까지의 숫자 중 하나를 정한 뒤, 해당 숫자를 맞추기 위해 숫자를 하나 말하면 “UP” 또는 “DOWN”으로 힌트를 주는 게임과 유사한 알고리즘이다.

이전 포스트에서 살펴본 투 포인터는 불가능한 경우를 제거하며 탐색하는 방식이다. 이분 탐색도 같은 원리를 활용하지만, 불가능한 경우를 절반씩 줄여 나간다는 점이 다를 뿐이다. 결국, 이분 탐색 역시 투 포인터를 활용해 구현할 수 있다.

코드 구현

N = int(input())
N_arr = sorted(list(map(int, input().split())))
M = int(input())
M_arr = list(map(int, input().split()))
answer = [0 for _ in range(M)]

for idx, num in enumerate(M_arr):
    s_p = 0
    e_p = N-1
    
    Flag = 0
    while s_p <= e_p:
        
        mid_p = (s_p + e_p)//2
        
        if N_arr[mid_p] == num: 
            Flag = 1
            break

        if N_arr[mid_p] < num:
            s_p = mid_p + 1
            continue
            
        if N_arr[mid_p] > num:
            e_p = mid_p - 1
            continue
        
    answer[idx] = Flag
    
print(*answer)

회고

경우의 수를 제거하는 방식은 같지만, 이분 탐색은 결국 탐색 알고리즘일 뿐이다. 투 포인터를 활용하긴 하지만, 특정 값을 찾는 것이 목적이며, 반면 투 포인터는 구간 합, 두 수의 합, 두 수의 차 등을 구하는 데 초점을 맞추므로 목적이 다르다.