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

백준 온라인저지 10816번 숫자 카드 2

문제풀러 바로가기👇👇👇👇👇👇

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

10816번: 숫자 카드 2

 

 

 

문제풀이

---

알고리즘 분류에는 이분 탐색으로 되어있는 문제다. 그러나 Counter 함수, 딕셔너리 등 여러 가지 방식으로 풀이할 수도 있는 문제이다.

그냥 단순히 배열의 메소드인 count()를 사용하면 시간초과가 발생하니 알아두자.

나는 bisect를 이용해 문제를 풀었다. 일단 이분탐색을 하려면 정렬된 배열이 대상이어야하기 때문에 배열을 먼저 정렬한다. 그리고 bisect_left와 bisect_right를 통해 타겟의 첫번째 인덱스와 마지막 인덱스를 알아내 마지막에 첫번째를 빼주면 그 수의 개수를 알아낼 수 있다.

 

 

내 코드

from bisect import bisect_left, bisect_right

n = int(input())
a = list(map(int, input().split()))
a.sort()

m = int(input())
target = list(map(int, input().split()))
for i in target:
    count = bisect_right(a, i) - bisect_left(a, i)
    print(count, end=" ")

 

 

다른 사람의 코드 - Counter 사용

from collections import Counter

input()
n_li = list(map(int, input().split()))
k = int(input())
m_li = list(map(int, input().split()))

cnt = Counter(n_li) 

for i in m_li :
    print(cnt[i], end = ' ')