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

예시

입력

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

---

나의 풀이

n = int(input()) # 갖고 있는 숫자 카드 개수 N
card = sorted(list(map(int, input().split()))) # 갖고 있는 숫자 카드 리스트(이진탐색을 위해 오름차순 정렬)
m = int(input()) # 탐색해야 할 숫자 카드 개수 M
target = list(map(int, input().split())) # 탐색해야 할 숫자 카드 리스트

cnt = [0 for _ in range(m)] # 탐색한 숫자 카드 카운팅 리스트 (0으로 초기화)

def bin_search(card, target, start, end): # 이진탐색 함수 정의
    while start <= end:
        mid = (start + end)//2

        if card[mid] == target:
            return 1

        elif card[mid] > target:
            end = mid - 1

        else:
            start = mid + 1

    return 0


for i in range(m):
    cnt[i] += bin_search(card, target[i], 0, n-1)

# 정답출력
for i in range(m):
    print(cnt[i], end = ' ')

근데 틀렸음
결과가 이렇게 나왔다

# 입력
10
6 3 2 10 10 10 -10 -10 7 3
8
10 9 -5 2 3 4 5 -10

# 출력
1 0 0 1 1 0 0 1 

틀린 이유

주어진 숫자 카드 N개에는 중복된 카드도 있어서 카드 별 개수를 누적해서 카운팅 해야 하는데 그 부분 구현하는 방법을 몰랐다.
즉, 리스트 cnt를 탐색할 숫자 카드의 번호(key)와 카운팅 횟수(value)로 이루어진 딕셔너리로 바꿔줘야 한다.

---

다른 사람 풀이 (1)

n = int(input())
card = sorted(list(map(int, input().split())))
m = int(input())
target = list(map(int, input().split()))

cnt = {}

def binary_search(card, target, start, end):
    while start <= end:
        mid = (start + end)//2

        if card[mid] == target:
            return cnt.get(target)

        elif card[mid] > target:
            return binary_search(card, target, start, mid-1)

        else:
            return binary_search(card, target, mid+1, end)
    return 0

# 탐색한 카드 별 카운팅 횟수 누적
for i in card:
    if i in cnt:
        cnt[i] += 1
    else:
        cnt[i] = 1

# 정답출력
for i in target:
    print(binary_search(card, i, 0, n-1), end = ' ')

다른 사람 풀이 (2)

n = int(input())
card = sorted(list(map(int, input().split())))
m = int(input())
target = list(map(int, input().split()))

cnt = {}

for i in card:
    if i in cnt:
        cnt[i] += 1
    else:
        cnt[i] = 1

for i in target:
    if i in cnt:
        print(cnt[i], end = ' ')
    else:
        print(0, end = ' ')

---

알게된 것

✓ 딕셔너리 객체 메소드 딕셔너리명.get()

딕셔너리 자료구조에서 '키'에 해당하는 '값'을 참조하고 싶을 때 사용하는 메소드

딕셔너리명.get(key, default = None) # 참조하고자 하는 키가 존재하지 않는다면 'None'을 리턴한다.

---

References

get() 메소드 개념 참고
참고한 풀이