[백준] 10816. 숫자 카드 2 - 파이썬 풀이

백준 숫자카드2

풀이

• 일단 처음에 문제를 보고 입력이 500,000까지의 범위에 시간 제한이 1초인 것을 보고 문제를 최소한 O(n^2) 이하의 알고리즘으로 구현해야겠다고 생각했다. 입력을 보고 이런 생각을 하는 것을 연습중인데 꽤나 도움이 되는 것 같다.
• 시간 내에 몇개의 원소가 있는지 확인하려면 Hash를 사용하여 숫자를 Counting하여 비교하면 되겠다고 생각했다.
  • 이를 구현하기 위해서 collections.Counter 라이브러리를 사용했다.
• Counter 라이브러리의 결과값을 타겟 리스트(m_list)와 비교하여 타겟 리스트의 요소가 Counter 결과값에 존재하면 counting 한 value 값을 프린트 해주면 된다.

from collections import Counter  
import sys  

sys.stdin = open("10816_숫자카드2_input.txt", "r")  
n = int(sys.stdin.readline())  
n_list = list(map(int, sys.stdin.readline().split()))  
n_counter = Counter(n_list)  
m = int(sys.stdin.readline())  
m_list = list(map(int, sys.stdin.readline().split()))  

print(' '.join(str(n_counter[m]) if m in n_counter else '0' for m in m_list))

시간 초과 없이 통과하는 것을 확인할 수 있다.