[백준 실버4] 10816 숫자카드2.py

<문제 설명>

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

10816번: 숫자 카드 2

숫자 카드는 정수 하나가 적혀져 있는 카드이다. 상근이는 숫자 카드 N개를 가지고 있다. 정수 M개가 주어졌을 때, 이 수가 적혀있는 숫자 카드를 상근이가 몇 개 가지고 있는지 구하는 문제이다.

 

입출력의 예는 다음과 같다.

예제 입력 1 복사

10
6 3 2 10 10 10 -10 -10 7 3
8
10 9 -5 2 3 4 5 -10

예제 출력 1 복사

3 0 0 1 2 0 0 2

 

 

<문제 해결 아이디어>

처음엔 그냥 리스트에 숫자가 있는지 파악한 후 수를 세서 리턴하는 코드를 짰다. 그리고 시간 초과가 떠서 고민을 하던 중 딕셔너리로 푸는 다른 코드를 보고 힌트를 얻어 코드를 다시 작성했다. 받은 배열 두 개를 정렬한 후 사용했고, 이미 한번 개수를 센 숫자는 다시 세지 않도록 했다.

 

<문제 풀이 코드>

import sys
num1 = sys.stdin.readline()
N = sorted(map(int,sys.stdin.readline().split()))
num2 = sys.stdin.readline()
M = list(map(int,sys.stdin.readline().split()))
index, m_dic = 0, {}

for m in sorted(M):
    cnt = 0
    if m not in m_dic:
        while index < len(N):
            if m == N[index]:
                cnt += 1; index += 1
            elif m > N[index]:
                index += 1
            else: break
        m_dic[m] = cnt
answer = ' '.join(str(m_dic[m]) for m in M)
print(answer)

채점 결과