[BOJ/백준] 10816 숫자 카드 2

문제

숫자 카드는 정수 하나가 적혀 있는 카드이다. 상근이는 숫자 카드 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개의 수에 대해서, 각 수가 적힌 숫자 카드를 상근이가 몇 개 가지고 있는지를 공백으로 구분해 출력한다.

---

예제 입/출력

 

풀이

 

처음에는 Count함수를 사용해서 문제를 풀었다 . 하지만 count함수의 시간 복잡도는 O(N^2)라서 계속해서 시간 초과로 실패했다. 그래서 이진 탐색으로 풀려고 했는데 쉽지 않아 다른 사람들이 어떻게 풀었는지 참고했다. 그냥 이진 탐색으로 풀었던 분도 계시고 dic, Hash알고리즘을 이용해서 푸신분들도 계셨다. 그 가운데 나는 저번에 참고했었던 Collections 라이브러리에 있는 Counter를 이용해서 풀었다. 그래도 이진 탐색으로 풀었던 코드도 같이 첨부해서 참고해야겠다.

 

#dic을 이용한 풀이
import sys

n = map(int,sys.stdin.readline())
keyList = list(map(int,sys.stdin.readline().split()))
dic = {} #딕셔너리 선언

for k in keyList:
  if k not in dic:
    dic[k] = 1
  else:
    dic[k] += 1

m = map(int,sys.stdin.readline())
target = list(map(int,sys.stdin.readline().split()))

for t in target:
  if t in dic:
    sys.stdout.write(str(dic[t])+" ")
  else:
    sys.stdout.write("0 ")

 

#collections라이브러리 Cunter함수 활용

_= 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))

 

 

#이진탐색

from sys import stdin

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

def binary_serarch(n,N,start,end):
  if start > end:
    return
  mid = (start + end) //2
  if n == N[mid]:
    return N[start:end+1].count(n)
  elif n <N[mid]:
    return binary_serarch(n,N,start,mid-1)
  else:
    return binary_serarch(n,N,mid+1,end)

dic = {}
for i in N:
  start = 0
  end = len(N) -1
  if i not in dic:
    dic[i] = binary_serarch(i,N,start,end)

print(' '.join(str(dic[x]) if x in dic else '0' for x in M))

 

정답

---

느낀 점

아직 갈길이 한참 멀다.. 기본적인 문제는 풀 수 있지만 조금이라도 응용을 하려고 하면 뇌가 굳어버리는 느낌.

아직 사고력이 많이 부족한 것 같다. 다양한 문제를 풀어보고 이론도 공부하고 기초를 다져서 기본을 탄탄하게 하고서 문제를 풀어봐야겠다. Counter , dic , stdin , out 등 공부해서 게시해야겠다.