[맛있는물회] [파이썬] <백준 알고리즘> 10816번 "숫자 카드 2"

문제 조건

---

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

 

Input

---

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

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

 

Output

---

첫째 줄에 입력으로 주어진 M개의 수에 대해서, 각 수가 적힌 숫자 카드를 상근이가 몇 개 가지고 있는지를 공백으로 구분해 출력한다.

 

생각한 아이디어

---

수찾기 문제랑 아주 유사하지만 다른듯한..문제.. ㅋㅋㅋㅋㅋㅋㅋㅋㅋ

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

1920번: 수 찾기

 

값이 존재하는지 찾는 로직은 같다.

하지만 개수를 찾는 것이 이 문제의 키포인트이다.

 

맨첨에는 값을 찾으면 값의 시작점까지 while 문을 돌고, 끝점까지 다시 while문을 돌았는데 시간초과가 발생했다.

생각해보니 만약 input 값이

1 2 2 2 2 2 2 2 2 2 2 2 2 2... 이렇게 500000개가 있다면?

 

그렇게 되면 최악의 경우 시간 복잡도가 완전탐색과 동일하게 된다.

이 문제에서는 이러한 풀이를 원하는 것이 아니기 때문에 다른 방법으로 접근을 해보았다.

맨첨에는 dictionary를 만들어서 싹 다 개수를 세볼까 하다가 아닌 것같아서 고민했다.

 

그렇게 Counter 모듈을 사용했다.

 

될지 의문이었는데 되어서 다행이다. ㅎㅎ

 

Counter 모듈을 사용해서 input값의 각각 값마다 개수를 저장한다.

그리고 set으로 중복값을 없애주고 이를 바탕으로 하여 이전의 이진탐색을 수행한다.

 

그리고 output은 아까 만들어놓은 counter에서 불러오기!

 

소스코드

import sys
import operator
from collections import Counter
input=sys.stdin.readline

def find(target,arr,counter):
   front,rear=0,len(arr)-1
   flag=False
   cnt=0
   while rear>=front:
      mid=(front+rear)//2
      if arr[mid] >= target:
         if arr[mid]==target:
            flag=True
            break
         rear=mid-1
      else:
         front=mid+1
   
   if flag:
      cnt=counter[target]
   return cnt


if __name__ == "__main__":
   n=int(input())
   arr1=list(map(int,input().split()))
   m=int(input())
   arr2=list(map(int,input().split()))

   counter = dict(Counter(arr1))
   arr1=sorted(set(arr1))
   tmp=[]
   for a in arr2:
      tmp.append(find(a,arr1,counter))
   print(*tmp)

 

*파이썬 문법 정리