문제 설명

전체 코드

import sys

input = sys.stdin.readline

def binary(i, card_n, start, end):
    if start > end:
        return 0

    mid = (start + end) // 2

    if i == card_n[mid]:
        return card_n[start:end+1].count(i)
    elif i < card_n[mid]:
        return binary(i, card_n, start, mid-1)
    else:
        return binary(i, card_n, mid+1, end)


n = int(input())
card_n = list(map(int, input().split()))
card_n.sort()

m = int(input())
card_m = list(map(int, input().split()))

n_dic = {}    

for i in card_n:
    start = 0
    end = len(card_n) - 1
    if i not in n_dic:
        n_dic[i] = binary(i, card_n, start, end)

for i in card_m:
    if i in n_dic:
        print(n_dic[i], end=" ")
    else:
        print(0, end=" ")

해결 방법

n과 card_n 리스트 그리고 m과 card_m변수를 선언하고 값을 입력받는다. 그 후 card_n을 오름차순으로 정렬한다. 그리고 여기서 만약 card_n의 count를 무지성으로 작성한다면 시간초과가 나는 것을 볼 수 있다. 이 문제는 이분탐색을 사용하여 풀라는 의도로 만들어진 문제로 먼저 card_n을 for문을 사용하여 i원소가 선언되어있는 n_dic 딕셔너리에 원소로 없으면 n_dic[i]에 값을 넣어주기 위한 start = 0, end = len(card_n)-1로 이분탐색을 하는 binary함수를 시작한다.

binary함수 안에서는 먼저 start > end 이면 0을 리턴해주고, 이분탐색의 특징인 반으로 나누기 mid = (start+end)//2을 해준다. 그 후 i가 card_n[mid]이라면 이때 start와 end+1 사이에 있는 리스트에서 card_n의 i를 count해주고 return 한다. 만약 그게 아닌 i < card_n[mid]이라면 end = mid-1을 해주고 binary함수를 재귀로 다시 돌린다. 만약 i > card_n[mid]라면 반대로 start = mid+1을 해주고 binary함수를 재귀로 다시 돌린다. 그 결과 card_n의 각 원소의 갯수들이 n_dic 딕셔너리에 넣어지게 된다.

마지막으로 card_m에 있는 원소들이 n_dic의 key값에 있으면 그 value를 출력하고 그게 아니면 0을 출력한다.

• 이분탐색의 가장 기초적인 문제이므로 외우자