문제

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

입력
첫째 줄에 상근이가 가지고 있는 숫자 카드의 개수 N(1 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 숫자 카드에 적혀있는 정수가 주어진다. 숫자 카드에 적혀있는 수는 -10,000,000보다 크거나 같고, 10,000,000보다 작거나 같다.

셋째 줄에는 M(1 ≤ M ≤ 500,000)이 주어진다. 넷째 줄에는 상근이가 몇 개 가지고 있는 숫자 카드인지 구해야 할 M개의 정수가 주어지며, 이 수는 공백으로 구분되어져 있다. 이 수도 -10,000,000보다 크거나 같고, 10,000,000보다 작거나 같다.

출력
첫째 줄에 입력으로 주어진 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

N = int(sys.stdin.readline().strip())
nums = sys.stdin.readline().strip().split(' ')
M = int(sys.stdin.readline().strip())
check = sys.stdin.readline().strip().split(' ')

answer = ''
for c in check:
    cnt = 0
    for num in nums:
        if c == num:
            cnt += 1
    answer += (str(cnt)+' ')

print(answer.strip())

🎈 완성 코드

위처럼 10이 3개인 걸 찾기 위해서 굳이 3번 돌면서 처리하면 너무 오래 걸린다. 일단 "10은 3개 있다" 라고 만들어놓고 시작하고 싶었다.
그래서 nums 리스트를 딕셔너리 (key - 숫자 / value - 숫자 개수)로 만들어주었다.
검색하던 중 try except 구문을 활용해 만드는 신박한 방법이 있어서 적용해보았다.

# 900ms
import sys

N = int(sys.stdin.readline().strip())
nums = sys.stdin.readline().strip().split(' ')
M = int(sys.stdin.readline().strip())
check = sys.stdin.readline().strip().split(' ')

dic = {}
for num in nums:
    try: dic[num] += 1
    except : dic[num] = 1

answer = [0]*len(check)
for i in range(len(check)):
    try: answer[i] = dic[check[i]]
    except: answer[i] = 0

print(' '.join(map(str, answer)))

처음 코드로는 반복문이 중첩돼있어 (nums 길이 * check 길이)만큼 반복을 해야 하는데, 위 코드로는 (nums 길이 + check 길이) 만큼만 하면 되니 통과할 수 있었다 ^_^

코드 최적화

사실 리스트 요소의 개수를 가지고 딕셔너리를 만들려면 저렇게 try except 쓸 필요도 없이 파이썬 coellections 모듈의 Counter 클래스를 사용하면 된다.
예전에 몇번 활용해봤던것 같은데 아직도 익숙하지 않아서 바로 떠오르지 않는다ㅠ

# 720ms
import sys
from collections import Counter

N = int(sys.stdin.readline().strip())
nums = Counter(sys.stdin.readline().strip().split(' '))
M = int(sys.stdin.readline().strip())
check = sys.stdin.readline().strip().split(' ')

answer = ['0']*len(check)
for i in range(len(check)):
    try: answer[i] = nums[check[i]]
    except: pass

print(' '.join(map(str, answer)))

💡 파이썬 Counter 클래스 사용하기

from collections import Counter
# 원소 개수 구하기
Counter('hello')  # {'h':1, 'e':1, 'l':2, 'o':1}
# 최빈순으로 정렬된 배열 리턴
Counter('hello').most_common()  # [('l',2), ('h',1), ('e',1), ('o',1)]
# most_common 함수에 인자 K를 주면 => 최빈순 K개의 데이터
Counter('hello').most_common(1)  # [('l',2)]