백준 10816 풀이 (숫자 카드 2, 이분 탐색, 해쉬 사용, Counter)

이번 문제는 Counter를 사용해서 해결했다. 기본적인 이분 탐색과 풀이에 차이가 전혀 없다. 단지 Counter를 이용해서 Dict형태로 만들어 주고 중복값을 제거하여 이분 탐색을 진행하게 만들었다.

1. Counter를 이용해서 중복을 제거한 Adict를 얻는다.

2. Adict에서 key값만 뽑아서 중복이 제거된 Alist를 얻는다.

3. Alist를 오름차순으로 정렬한다.

4. 이분탐색을 이용하여 해당되는 값을 구한다.

5. 해당 되는 값을 구할 수 있다면 Adict에서 몇개나 존재하는지 출력한다.

위의 순서로 코딩을 진행하면 쉽게 풀 수 있다.

from collections import Counter
n = int(input())
AC = Counter(list(map(int, input().split())))
Akey = list(AC.keys())
Akey.sort()
m = int(input())
B = list(map(int, input().split()))

def find(A,start, end,i):
    while start <= end :
        mid = (end+start)//2
        if A[mid] == i or A[end] == i:# mid가 맞으면
            return print(AC[i])
        elif A[mid] < i: # 오른쪽에 있음
            start = mid+1
        else: # 왼쪽에 있음
            end = mid-1
    return print(0)

for i in B:
    find(Akey,0,len(Akey)-1,i)

다른 고수들의 풀이를 보니 dictionary에 넣고 차례로 뽑아내는 방법을 사용하기도 한다. 이 방법을 사용하면 상당히 코드가 간단해진다. 그리고 if A in Blist:로 탐색을 하게 되는데 비교하는 숫자 자체가 작아지기 때문에 상당히 빠른 시간에 해결된다.(내 코드가 그냥 비효율적이다ㅋㅋㅋㅋ)

위에가 hash를 써서 아래의 코드로 돌린거

n = int(input())
A  = map(int, input().split())
m = int(input())
B = list(map(int, input().split()))

hashmap = {}
for n in A:
    if n in hashmap:
        hashmap[n] += 1
    else:
        hashmap[n] = 1

for m in B:
    if m in hashmap:
        print(hashmap[m])
    else:
        print(0)

결론은 효율적으로 생각하자!