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

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

10816번: 숫자 카드 2

 

 

# 조건

• 숫자 카드는 정수 하나가 적혀있다.
• N개의 숫자카드를 입력 받는다
• 이후 주어지는 M개의 카드가 주어질 때 '같은 번호'의 카드가 몇 개인지 출력하라

 

# 접근 방법 및 SOLUTION

• 리스트를 정렬 후 counter 메서드를 이용하여 푸니 시간초과가 발생하였다.
• 이진 탐색 또는 딕셔너리를 활용해주는 것이 바람직해 보였고
• 딕셔너리 내에 각 카드 숫자의 개수를 기록한 후 한꺼번에 출력
• COUNTER 함수를 이용하여 리스트를 담아주면 자동으로 DICTIONARY 형태로 바꿔주는 것을 알게 되었다.

 

# 시간초과 코드

N = int(input())
num = list(map(int, input().split()))

M = int(input())
target = list(map(int, input().split()))
for i in target:
    print(num.count(i), end= ' ')

 

1. DICTIONARY 활용

import sys
input = sys.stdin.readline

N = int(input())
num = list(map(int, input().split()))
num.sort()
M = int(input())
target = list(map(int, input().split()))
hash = {}
for i in num:
    if i in hash:
        hash[i] +=1
    else:
        hash[i] = 1

print(' '.join(str(hash[j]) if j in hash else '0' for j in target))

 

2. 이분 탐색 활용

import sys
input = sys.stdin.readline

_ = stdin.readline()  
N = sorted(map(int,stdin.readline().split()))  
_ = stdin.readline()  
M = map(int,stdin.readline().split())

def binary(n, N, start, end):  
    if start > end:  
        return 0  
    m = (start+end)//2  
    if n == N[m]:  
        return N[start:end+1].count(n)  
    elif n < N[m]:  
        return binary(n, N, start, m-1)  
    else:  
        return binary(n, N, m+1, end)  
  
n_dic = {}  
for n in N:  
    start = 0  
    end = len(N) - 1  
    if n not in n_dic:  
        n_dic[n] = binary(n, N, start, end)  
  
print(' '.join(str(n_dic[x]) if x in n_dic else '0' for x in M ))

 

3. COUNTER 함수활용

from sys import stdin  
from collections import Counter  
_ = stdin.readline()  
N = stdin.readline().split()  
_ = stdin.readline()  
M = stdin.readline().split()  
  
C = Counter(N)  
print(' '.join(f'{C[m]}' if m in C else '0' for m in M))