[백준/python]10816번 숫자 카드2 - binary search

10815번의 변형 문제이다. 해당 문제를 푸는 여러 풀이가 있지만 어떤 풀이를 선택하든 딕셔너리(해쉬맵)을 사용해야 시간 내에 풀 수 있다.

10815번과 다르게 이진 탐색의 범위를 줄여줄 때 mid에 +-1 을 하지 않고 범위를 줄이는 방식을 선택했다. 이렇게 하기 위해서는 초기에 s와 t를 리스트이 범위[0,N-1]보다 넓게[-1,N] 설정해주어야 루프의 조건이 t-s>1 일 때 리스트의 맨 처음과 끝까지 탐색할 수 있다. 관련 내용은 이후에 정리할 예정이다.

1.

N = int(input())
card = list(map(int, input().split()))
M= int(input())
question = list(map(int, input().split()))
card = sorted(card)
count=[1 for _ in range(N)]

i=1
while True:
    if len(card)==i:
        break
    
    if card[i] == card[i-1]:
        card.pop(i)
        count[i-1]+=1
        count.pop(i)
    else:
        i+=1    
N=len(card)

answer=[0 for _ in range(M)]
for i in range(M):
    s ,t = -1, N #시작 범위 설정 주의
    check = question[i]

    while t-s>1:
        mid = (s+t)//2

        if check == card[mid]:
            answer[i]=count[mid]
            break
        elif check > card[mid] :
            s,t= mid,t
        elif check < card[mid]:
            s,t= s,mid
                
for i in range(M):
    print(answer[i], end=' ')

*주어진 카드를 정렬하고 중복된 카드는 배열에서 삭제하고 해당 카드의 인덱스에 대응되는 배열을 만들어 카드의 개수를 저장한다.
M개의 0을 가진 answer 배열을 만든다. 이진 탐색을 돌려가며 질문에 해당되는 카드가 있으면 answer배열에 카드의 개수를 담아둔다.

2.

N = int(input())
card = list(map(int, input().split()))
M= int(input())
question = list(map(int, input().split()))
card = sorted(card)
count=[1 for _ in range(N)]

dic={}

for c in card:
    if c in dic:
        dic[c]+=1
    else:
        dic[c]=1

# print(dic)

answer=[0 for _ in range(M)]
for i in range(M):
    s ,t = -1, N #이렇게 설정하면 된다. 10815와 비교
    check = question[i]

    while t-s>1:
        mid = (s+t)//2

        if check == card[mid]:
            answer[i]=dic[check]
            break
        elif check > card[mid] :
            s,t= mid,t
        elif check < card[mid]:
            s,t= s,mid
                
for i in range(M):
    print(answer[i], end=' ')

*카드의 개수가 담긴 딕셔너리를 만든다.
이진 탐색을 통해 해당 카드를 발견하면 1번의 풀이와 마찬가지로 answer 배열에 카드의 개수를 저장한다.