[BOJ 10815] 숫자 카드 (Python)

박지훈·2021년 5월 2일
0

[BOJ 10815] 숫자 카드 (Python)



풀이

처음에 상근이가 가지고 있는 카드 리스트에 사용할 인덱스 포인터 1개, 주어진 카드(체크할 카드)에 사용할 인덱스 포인터 1개로 총 2개의 인덱스 포인터를 사용하는 방식으로 접근하였다.
2개의 카드 리스트를 오름차순 정렬 후에 상근이 카드가 주어진 카드보다 크면 주어진 카드의 인덱스 포인터를 +1하고, 그 반대이면 상근이 카드의 인덱스 포인터를 +1하며, 2개의 카드가 같다면 2개의 인덱스 포인터를 모두 +1 하여 답을 구하는 방식으로 구현하였다. 하지만, 시간 초과가 발생하였다. 아마 while문의 조건 혹은 for문 안의 if in문으로 인해 O(N*M) = O(N^2)(문제에서 N과 M의 크기가 같음)의 시간 복잡도를 가지기 때문인 것 같다. (if in문은 모든 리스트를 전부 훑어보기 때문에 O(N)의 시간 복잡도를 가진다고 한다.)

그래서 생각한 것은 이분 탐색이었다. 이분 탐색을 사용하면 O(NlogN)의 시간 복잡도로 줄일 수 있기 때문이다. 이분 탐색을 알고 있다면 쉽게 구현할 수 있을 것이라 생각한다. 상근이가 가지고 있는 카드를 오름차순 정렬한 후 주어진 카드에서 한 장씩 뽑아 상근이가 가지고 있는 카드 뭉치에 있는지를 반복하면 된다. (상근이가 가지고 있는 카드를 오름차순으로 정렬한 이유는 이분 탐색을 사용하기 위해서이다. 이분 탐색은 오름차순으로 정렬된 리스트에서 가능하기 때문이다.)



코드

import sys

input = sys.stdin.readline
N = int(input())
card = list(map(int, input().split()))
M = int(input())
check = list(map(int, input().split()))

# 이분 탐색을 위한 오름차순 정렬
card.sort()

answer = [0] * M
# 이분 탐색 진행
for i in range(M):
    left = 0
    right = N - 1
    while left <= right:
        mid = (left + right) // 2
        if card[mid] == check[i]:
            answer[i] = 1
            break
        elif card[mid] < check[i]:
            left = mid + 1
        else:
            right = mid - 1

print(*answer)
profile
Computer Science!!

0개의 댓글