[Python] 백준 10816번 숫자 카드 2

문제

https://www.acmicpc.net/problem/10816

풀이과정

• 가지고 있는 카드의 갯수, 카드의 종류를 입력
• 찾아야하는 카드의 갯수, 카드의 종류를 입력

첫시도

처음 시도는 단순하게 이중 for문으로 시도했다가 시간초과가 발생했다.

import sys

n = int(sys.stdin.readline())
n_list = list(map(int, sys.stdin.readline().split()))
m = int(sys.stdin.readline())
m_list = list(map(int, sys.stdin.readline().split()))  # 해당 숫자를 몇개 가지고 있는지

for i in m_list:
    cnt = 0
    for j in n_list:
        if j == i:
            cnt += 1
    print(cnt, end=' ')

두번째 시도

시간을 줄이기 위해서 탐색과정이 어떤 것이 있을까 고민하다가 탐색에는 선형, 이진, 해시가 있는데 이진 탐색을 사용하면 좋을 것 같다.

이진탐색은 자료가 정렬되어 있어야 한다.

가지고 있는 카드의 갯수만 정렬되어 있으면 그것을 기준으로 탐색을 시도한다.

풀어보다가 무언가 이상하고 시간이 많이 소요되어서 다른 코드를 참고하였다.

import sys

n = int(sys.stdin.readline())
cards = list(map(int, sys.stdin.readline().split()))
cards.sort()
m = int(sys.stdin.readline())
targets = list(map(int, sys.stdin.readline().split()))  
index, m_dic = 0, {}
# targets의 원소가 key, 해당 원소가 몇개 있는지 value

for i in sorted(targets):  # sorted(targets)에 해당하는 값만
    cnt = 0
    if i not in m_dic: # i가 m_dic에 있는지 확인 -> 처음에 등장하는 것만 처리
        while index < len(cards): # 카드의 길이만큼 수행
            if i == cards[index]: # 값이 존재하는 경우 
                cnt += 1
                index += 1
            elif i > cards[index]: # 확인하려는 값이 크면, 다음 원소를 확인
                index += 1
            else:
                break
        m_dic[i] = cnt
print(' '.join(str(m_dic[i]) for i in targets))

이진탐색 + 중복계산방지로 시간을 줄여주는 코드이다.
딕셔너리의 사용법도 다시 확인하고 혼자 구현할 수 있을 만큼 더 분석하고 시도해봐야겠다.