10815 숫자카드

1. 문제

문제는 링크에 들어가면 있다.

2. 정답 코드

문제의 내 정답 코드는 다음과 같다.

import sys
read = sys.stdin.readline


def binary(N_list, start_idx, end_idx, M):

    while start_idx <= end_idx:

        mid_idx = (start_idx + end_idx) // 2
        if N_list[mid_idx] == M:
            return 1
        elif N_list[mid_idx] < M:  # mid를 오른쪽으로 -> start_idx = mid_idx+1
            start_idx = mid_idx + 1
        elif N_list[mid_idx] > M:  # mid를 왼쪽으로 -> end_idx = mid_idx -1
            end_idx = mid_idx - 1

            # 만약 찾지 못하고 그냥 끝나버리면 -1 return
    return 0

N = int(read())
N_list = list(map(int,read().split()))
M = int(read())
M_list = list(map(int,read().split()))

# M에 대해 N_list를 훑으면 최대 500000*500000의 연산이 발생해 하나씩 훑는건 불가능
# 따라서 빠르게 탐색하는 방법을 찾아야한다. -> 이분 탐색
N_list.sort()

start_idx = 0
end_idx = len(N_list)-1

for m in M_list :
    print(binary(N_list,start_idx,end_idx,m), end=' ')

3. 생각 및 풀이

생각

이 문제는 일반적인 순차탐색으론 최대 50만*50만의 반복문을 사용하므로 다른 탐색법으로 접근해야했다. 그래서 빠른 탐색법인 이분탐색을 활용한다.

문제 풀이

먼저 상근이가 갖고있는 숫자카드를 정렬한 후, 이분탐색을 시작하면 된다. 기본적인 이분탐색과 틀이 갖기 때문에 특별한 설명은 생략한다.