백준 10816번: 숫자 카드 2 -이분탐색 (Python)

접근

굉장히 오랜 시간을 투자하여 푼 문제이다. 이분탐색 알고리즘을 이용하여 풀기 위해 최적화에 최선을 다하여 결국엔 제한 시간 내에 들어오는 코드를 작성하였다. 더 최적화시킬 방법을 배우기 위해 다른 분들의 코드를 찾다보니 10줄 내외로 완성되는 dictionary를 이용한 간단한 방법도 있었다. 이 방법으로도 풀어봤고 다음 글에 정리해볼 예정이다.

먼저 이분탐색 알고리즘은 오름차순으로 정렬된 리스트의 중간값과 찾고자 하는 값을 비교하여 중간값보다 찾고자 하는 값이 클 경우 중간값부터 끝 값까지, 찾고자 하는 값이 더 작을 경우 첫 값부터 중간값까지의 리스트를 가지고 다시 중간값 탐색을 하는 알고리즘이다. 바로 전 문제가 이분탐색 알고리즘을 이용한 아주 기본 문제였다.

2021.04.05 - [코딩/백준 (Python)] - 백준 1920번: 수 찾기 (Python)

백준 1920번: 수 찾기 (Python)

이번 문제를 해결하기 위한 시행착오들을 정리해보았다.

1. 주어진 리스트에서 목표값을 이분탐색하고 해당 값을 삭제, 해당 리스트를 계속해서 이분탐색하여 목표값이 없을 때까지 반복하여 해당 목표값이 리스트에 몇개있는지 탐색 (시간 초과)
2. 주어진 리스트에서 목표값을 이분탐색하고, 해당 값을 기준으로 좌우로 한칸씩 진행하면서 목표값이 몇개 있는지 확인 (시간 초과)
3. 2번 방법에 더하여, dictionary를 이용하여 넷째 줄에 주어진 수 중 중복 탐색을 생략하는 방법 (해결)

코드

import sys


def binarysearch(array, start, end, target):
    if start > end:
        return 0
    mid = (start + end) // 2
    if target == array[mid]:  # 목표 값 탐색 시 좌우로 진행하면서 목표 값 개수 확인
        a = mid
        b = mid
        cnt = 1
        while b < len(array):
            if array[b] != target:
                break
            else:
                cnt += 1
            b += 1
        while a >= 0:
            if array[a] != target:
                break
            else:
                cnt += 1
            a -= 1
        return cnt - 2
    elif target < array[mid]:
        return binarysearch(array, start, mid - 1, target)
    else:
        return binarysearch(array, mid + 1, end, target)


n = int(sys.stdin.readline())
a = list(map(int, sys.stdin.readline().split()))
m = int(sys.stdin.readline())
b = list(map(int, sys.stdin.readline().split()))
a.sort()
dic = {}
for n in a:
    if n not in dic:  # 같은 수 중복 탐색 생략
        dic[n] = binarysearch(a, 0, len(a) - 1, n)

print(' '.join(str(dic[c]) if c in dic else '0' for c in b))

더 생각해 볼 것?

이분탐색 알고리즘을 이용하는 방법 중 더 최적화 할 수 있는 방법이 있는지 공부가 필요해보인다.

코드나 내용 관련 조언, 부족한 점 및 질문 언제든 환영합니다!