BOJ/백준-10816-python

문제

풀이

• 이분 탐색(이진 탐색) 알고리즘으로 접근하였다.
• 입력 데이터와 탐색 범위가 매우 넓은 편이라 sys라이브러리의 readline 함수를 이용하여 입력 속도를 줄였다.
• 이진 탐색을 구현하기 위해 탐색할 list 데이터를 sort한 뒤, 중복된 데이터의 개수를 dict으로 할당하였다.
• 이후 해당 데이터가 있는지 없는지 이진 탐색으로 하나하나 요소를 확인해가며 체크한 뒤, true false를 반환하도록 구현하였다.

코드

# https://www.acmicpc.net/problem/10816
# boj, 10816: 숫자 카드 2, python3
import sys

input = sys.stdin.readline

def solve(array, target, start, end):
    while start <= end:
        mid = (start+end)//2

        if array[mid] == target:
            return True
        elif array[mid] > target:
            end = mid - 1
        else:
            start = mid + 1

    return None

if __name__ == '__main__':
    n = int(input())
    card_list = sorted(map(int, input().split()))
    m = int(input())
    sanggeun_list = list(map(int, input().split()))
    duplicate_cnt = {}
    result = [0] * m

    for i in card_list:
        if i not in duplicate_cnt:
            duplicate_cnt[i] = 1
        else:
            duplicate_cnt[i] += 1

    for x in range(len(sanggeun_list)):
        if solve(card_list, sanggeun_list[x], 0, n-1):
            result[x] = duplicate_cnt[sanggeun_list[x]]

    print(*result)

결과

출처 & 깃허브

boj 10816
github