[Baekjoon, Python] 10816번: 숫자 카드 2

도입

백준 단계별 풀기에서 이분탐색 두 번째 문제이다.

 

백준 10816번 문제, 입력, 출력

---

백준 10816번 입출력 예제 1

---

풀이

1. N개의 정수 카드가 있는데, 집합 M의 요소들이 들어있는지 확인하는 문제. 해당 num이 들어왔을 때, N을 이분탐색을 하여서 있는 만큼 카운트하여 출력

 

2. binarySearch 함수를 만들어서 분할정복을 통해 해결. 하지만, 추가적으로 알게된 사실이지만, 이미 파이썬에서는 Collections 라이브러리의 Counter 함수가 해당 기능을 충분히 수행함. 

---

코드 1

from sys import stdin, stdout

_ = stdin.readline()        # Discard empty line
N = sorted(map(int,stdin.readline().split()))   # N[-10 -10 2 3 3 6 7 10 10 10]
_ = stdin.readline()        # Discard empty line
M = map(int,stdin.readline().split())           # M[10 9 -5 2 3 4 5 -10]

def binarySearch(num, N, start, end):       # 이분탐색 함수
    if start > end:         # start가 end보다 큰 경우
        return 0
    m = (start+end)//2      # mid
    if num == N[m]:
        i, j = 1, 1
        while m-i >= start: # mid기준 왼쪽
            if N[m-i] != N[m]:
                break
            else: i += 1
        while m+j <= end:   # mid기준 오른쪽
            if N[m+j] != N[m]:
                break
            else: j += 1
        return i + j - 1
    elif num < N[m]:
        return binarySearch(num, N, start, m-1)
    else:
        return binarySearch(num, N, m+1, end)

n_dict = {}             # 딕셔너리 자료형 선언
for n in N:
    start = 0           # 0
    end = len(N) - 1    # 9
    if n not in n_dict:  #
        n_dict[n] = binarySearch(n, N, start, end)

print(' '.join(str(n_dict[x]) if x in n_dict else '0' for x in M ))	# 구분자 ' '(공백)

코드 2

다른 방법을 서칭하는 중 Collections 라이브러리 안의 Counter 함수를 사용하면 더 빠른 속도를 가진 코드를 작성할 수 있음을 확인.

from sys import stdin
from collections import Counter

_ = stdin.readline()
N = stdin.readline().split()
_ = stdin.readline()
M = stdin.readline().split()

Count = Counter(N)	#카운터 함수 사용 
print(' '.join(f'{Count[m]}' if m in Count else '0' for m in M))

 

---

마무리

이분탐색의 알고리즘만 익혀두면, 이번 문제도 쉽게 해결 할 수 있다. 다만 놀랐던 것은 Collections 라이브러리를 사용함으로써, 시간을 많이 당길 수 있었다. goood