숫자 카드2 - 10816

1. 개요

문제 링크: https://www.acmicpc.net/problem/10816

2. 코드

import sys

def solve(target):
    global narr
    left_idx = 0
    right_idx = len(narr)
    lower_bound = upper_bound = -1

    # finding lower bound
    while right_idx > left_idx:
        mid_idx = (right_idx + left_idx) // 2
        if narr[mid_idx] < target:
            left_idx = mid_idx + 1
        else:
            right_idx = mid_idx
    lower_bound = left_idx

    # finding upper bound
    left_idx = 0
    right_idx = len(narr)
    while right_idx > left_idx:
        mid_idx = (right_idx + left_idx) // 2
        if narr[mid_idx] > target:
            right_idx = mid_idx
        else:
            left_idx = mid_idx + 1
    upper_bound = right_idx

    return upper_bound - lower_bound

n = int(sys.stdin.readline())
narr = list(map(int, sys.stdin.readline().split()))
m = int(sys.stdin.readline())
marr = list(map(int, sys.stdin.readline().split()))
narr.sort()

for i in marr:
    ans = solve(i)
    print(ans, end=' ')

3. 풀이 메모

첫번째 시도는 기존 이분 탐색 알고리즘을 활용해 검색값 target을 찾았다면, 그 지점을 기준으로 인덱스를 한칸씩 좌우로 넓혀가며 총 몇개의 동일 값이 있는지를 검색했다. 시간 복잡도는 최악의 경우 배열 내 모든 원소를 한번씩 순회하게 되므로 O(N)이고, 이 풀이의 경우는 시간 초과가 났다.

두번째 시도는 마찬가지로 이분 탐색으로 검색해 target의 위치를 찾고, 그 지점에서 좌우로 구역을 나누어 분할 정복을 시도했다. 하지만 분할 정복의 시간복잡도는 O(NlogN)이며, 당연히 첫번째 시도보다는 효율이 좋지 않았다. 만약 배열 내 모든 원소가 다 같은 값을 가지고 있다면, 어떤 가지 치기를 하더라도 최악의 경우에는 모든 원소를 탐색해야 할 것이다. 이 풀이의 경우도 시간 초과가 났다.

세번째 시도는 upper bound와 lower bound를 이용한 풀이다. 기존 이분 탐색 알고지름을 응용해, 해당 배열 내의 복수개의 같은 값이 존재한다면 그 값의 가장 왼쪽 인덱스와 가장 오른쪽 인덱스를 구할 수 있다.

1. upper_bound 알고리즘

while right_idx > left_idx:
        mid_idx = (right_idx + left_idx) // 2
        if narr[mid_idx] > target:
            right_idx = mid_idx
        else:
            left_idx = mid_idx + 1
    upper_bound = right_idx

2. lower_bound 알고리즘

while right_idx > left_idx:
        mid_idx = (right_idx + left_idx) // 2
        if narr[mid_idx] < target:
            left_idx = mid_idx + 1
        else:
            right_idx = mid_idx
    lower_bound = left_idx

알고리즘 초기 변수를 설정할 때 right_idx가 배열의 끝점(len(arr)-1)이 아닌 배열의 크기(len(arr))이어야 한다는 점에 유의한다.

4. 코멘트

lower_bound와 upper_bound를 몰라서 검색을 통해서 문제를 해결했다. 이분 탐색의 시간 복잡도가 O(logN)이라는 점을 유의해 모든 배열을 순회하는 알고리즘(O(N))을 코드 내에 포함시키지 않도록 작성해야 한다는 사실을 알게 되었다.