백준 10816번 숫자 카드 2

중복이 있는 경우 이분 탐색을 어떻게 사용할것인가?

이번 문제는 중복이 있을때 탐색 방법을 찾는 문제이다

 

문제 이해

입력을 받고 이진 탐색을 바로 이용하게 되면 제대로 탐색이 안될수 있다 이진 탐색의 알고리즘에서느 정렬이 되어있다고 하고 탐색을 하기 때문에 중복된 자료가 있는 경우에는 추가로 정리를 해줘야한다 이 문제를 해결 할 때 정렬 후 2중 리스트를 만들어 [i][0]에는 숫자를 저장하고 [i][1]에는 개수를 저장해야겠다라고 생각하고 문제를 풀었다 -> 시간초과로 파이썬 내장함수 이용

 

문제 해결

import sys
# 입력 받기
N = sys.stdin.readline().strip()

N_list = list(map(int,sys.stdin.readline().strip().split()))

M = sys.stdin.readline().strip()

M_list = list(map(int,sys.stdin.readline().strip().split()))

N_list_num = [] #2중 리스트로 [i][0]에는 숫자를 저장하고 [i][1]에는 개수를 저장

#입력받은 N_list 정렬한다
N_list.sort()

#정렬된 리스트에 이중리스트를 만드는 과정
t=1

for i in range(0,len(N_list)-1):

    if N_list[i] == N_list[i+1]:
        t += 1

    else:
        N_list_num.append([N_list[i],t])
        t = 1

if N_list[i] == N_list[i+1]:
    N_list_num.append([N_list[i],t])
else:
    N_list_num.append([N_list[i+1],1])



#이진 탐색
for i in M_list:
    start = 0
    end = len(N_list_num)-1
    a = 0 

    while start <= end:
        mid = (start + end)//2

        if N_list_num[mid][0] == i:
            print(N_list_num[mid][1])
            a = 1
            break

        elif N_list_num[mid][0] <= i:
            start = mid+1

        else:
            end = mid-1
    if a == 0:
        print(0)

첫번째로 이렇게 제출했는데 시간초과가 나왔다 또한 출력을 문제와 같이 만들지 않고 한줄씩 출력되게 만들었다 이부분을 바꿨도 시간초과가 나올것 같아서 파이썬 내장 함수를 이용하기로 했다

 

문제해결2

from collections import Counter를 추가하여 개수를 세주는 함수를 추가한다

from collections import Counter
import sys
# 입력 받기
N = sys.stdin.readline().strip()

N_list = list(map(int,sys.stdin.readline().strip().split()))

M = sys.stdin.readline().strip()

M_list = list(map(int,sys.stdin.readline().strip().split()))

N_list_num = []

#내장함수 Counter를 통해서 개수를 센다 -> 딕셔너리로 반환 된다
a = Counter(N_list)

#순차탐색
for i in M_list:
    if i in a:
        N_list_num.append(a[i])
    else:
        N_list_num.append(0)
# 문제대로 출력하기
for j in range(0,len(N_list_num)):
    if j == len(N_list_num)-1:
        print(N_list_num[j])

    else: # end ="문자"를 통해서 개행문자를 지우고 다른 문자를 넣을 수 있다
        print(N_list_num[j],end = " ")