[Baekjoon] 10816. 숫자 카드 2

문제 바로가기

[예제 입력]
10
6 3 2 10 10 10 -10 -10 7 3
8
10 9 -5 2 3 4 5 -10

[예제 출력]
3 0 0 1 2 0 0 2

🔍 첫 번째 코드 - 이진탐색, 딕셔너리

---

# 숫자 카드2 - 딕셔너리, 이분탐색

# 가지고 있는 카드
N = int(input())
n = list(map(int, input().split()))
n.sort() #이진탐색을 위해 정렬

# 몇 개 있는지 구해야 할 카드
M = int(input())
m = list(map(int, input().split()))

# 딕셔너리 생성 {카드번호:개수}
dic = {}
for i in n:
    if i in dic:
        dic[i] += 1
    else:
        dic[i] = 1

# 이진탐색 (가지고 있는 카드인지 확인하기 위한)
def binary_search(target):
    start = 0
    end = N-1

    while start <= end:
        mid = (start + end) // 2
        if n[mid] == target:
            return dic.get(target)
        elif n[mid] < target:
            start = mid + 1
        else:
            end = mid - 1
    return 0

# 카드 M개 - 가지고있는개수 출력
for i in m:
    print(binary_search(i), end= " ")

🔍 두 번째 코드 - 딕셔너리, key로 조회

---

# 숫자 카드2 - 딕셔너리 key로 조회

# 가지고 있는 카드
N = int(input())
n = list(map(int, input().split()))
n.sort() #이진탐색을 위해 정렬

# 몇 개 있는지 구해야 할 카드
M = int(input())
m = list(map(int, input().split()))

# 딕셔너리 생성 {카드번호:개수}
dic = {}
for i in n:
    if i in dic:
        dic[i] += 1
    else:
        dic[i] = 1

# 카드 M개 - 가지고있는개수 출력
for i in m:
    if i in dic: #가지고 있는 카드라면
        print(dic[i], end=" ") #개수(value) 출력
    else: #가지고 있지 않다면
        print(0, end=" ") #0을 출력

🔍 세 번째 코드 - Counter

---

# 숫자 카드2 - Counter

from collections import Counter

# 가지고 있는 카드
N = int(input())
n = list(map(int, input().split()))
n.sort() #이진탐색을 위해 정렬

# 몇 개 있는지 구해야 할 카드
M = int(input())
m = list(map(int, input().split()))

# 카드 수 세기
c = Counter(n)

# 출력
for i in m:
    if i in c:
        print(c[i], end = " ")
    else:
        print(0, end = " ")

🌀 collections.Counter

---

collections모듈의 Counter 클래스는 별도 패키지 없이 import해서 사용할 수 있다.

from collections import Counter

Counter 생성자는 여러 형태의 데이터를 인자로 받는다.
중복된 데이터가 저장된 배열을 인자로 넘기면 각 원소가 몇 번씩 나오는지가 저장된 객체를 얻게 된다.

ex_list = ['kim', 'kim', 'park', 'choi', 'kim', 'kim', 'kim', 'choi', 'park', 'choi']
ex_counter = Counter(ex_list)
print(ex_counter) #
print(type(ex_counter)) #

# 출력
Counter({'kim': 5, 'choi': 3, 'park': 2})
<class 'collections.Counter'>

Counter 클래스는 입력값을 순회하면서 연산을 수행하므로 N개의 원소를 가진 리스트를 한 번 순회하면서 Counter 객체를 구성하는 데 O(N) 시간이 걸린다. 

💫 Comment

처음엔 이진탐색으로 target을 찾고 target의 앞뒤에 target이 있는지 카운팅하는 방법을 생각했는데 시간초과가 났다.
문제 유형이 이진탐색이라 이진탐색밖에 생각하지 못했는데 딕셔너리나 Counter를 사용하는 방법이 있음을 알게되었다.

Reference
Reference