10816번: 숫자 카드 2 - 이분 탐색(Lower Bound, Upper Bound)

https://www.acmicpc.net/problem/10816

10816번: 숫자 카드 2

 

 

 

 

문제 분류는 일단 이분탐색으로 되어있지만 Hash Table 구조(Key, Value Pair)를 사용하여 해결할 수도 있다.

이분탐색(또는 이진탐색, Binary Search)은 오름차순으로 정렬되어 있는 리스트에서 특정한 값의 위치를 찾는 알고리즘이다.

정렬된 리스트에만 사용할 수 있지만, 매번 검색 범위가 반으로 줄기 때문에 O(logN)의 시간복잡도를 갖는다.

 

 

일단 이진탐색을 이용해 문제를 풀어보았다.

# NumerCard2.py

def BinarySearch(left, right, target):  
    mid = int((left + right)/2)

    # print ("{0} {1} {2} - {3}".format(left, mid, right, target))
    count = 0
    if target == cards[mid]:	# Target을 찾았다
        # print ("found on mid")
        midLeft = mid - 1
        count += 1
        while (midLeft >= 0 and target == cards[midLeft]):	# Target 왼쪽 카운팅
            # print ("found on mid Left")
            count += 1
            midLeft -= 1

        midRight = mid + 1
        while (midRight < len(cards) and target == cards[midRight]):	# Target 오른쪽 카운팅
            # print ("found on mid right")
            count += 1
            midRight += 1

        return count

    if (left > right or target < cards[left] or target > cards[right]):
        return count

	# 재귀적 이진탐색
    if target > cards[mid]:
        # print ("Right")
        return QuickSearch(mid + 1, right, target)
    elif (target < cards[mid]):
        # print ("Left")
        return QuickSearch(left, mid - 1, target)




### Input Parsing ###
N = int(input())
strCards = input()

cards = [int(i) for i in strCards.split(' ')]
cards.sort()	# 이진탐색을 위한 sorting
# print (cards)

M = int(input())
strGuesses = input()
guesses = [int(i) for i in strGuesses.split(' ')]

for i in guesses:
	print (QuickSearch(0, N - 1, i), end = " ")

 

 

Target의 위치까지 이진탐색을 하고, 

리스트에 중복된 값을 찾기 위해 해당 Index에서 왼쪽, 오른쪽으로 1칸씩 이동하며 counting을 해줬다.

(이진탐색은 리스트가 정렬되어 있어야하고, 중복된 값이 없어야 쓸 수 있다.)

 

여러 예제를 돌려보니 답은 맞게 나오는 것 같지만, 당연스레 시간초과가 발생한다.

이진탐색은 최악의 경우(값이 리스트에 없을 경우) 모든 Index를 돌기 때문에 O(N)의 시간 복잡도를 갖는다.

 

이럴 경우에 Lower Bound와 Upper Bound를 적용한다.

 

 

 

1) Lower Bound

Lower Bound는 정렬된 리스트에서 찾는 값 이상의 값이 처음 나오는 위치다.

cards = [1, 2, 3, 3, 3, 5]에서 3을 찾으면 Lower Bound는 index 2가 되고, 4를 찾는다면 Lower Bound는 index 5가 된다.

 

 

기본적인 구조는 이진탐색과 매우 비슷하다.

다만 target <= mid일 경우 현재 right이 lower bound일 수 있기 때문에 다음 right은 mid - 1이 아닌 mid로 잡아야한다.

 

cards = [1, 2, 3, 3, 3, 5], target = 3

1. left, mid, right = 0, 2, 5

left < right이라 탐색을 계속한다.

target "3" <= cards[mid] "3"이기 때문에  right = 2

 

2. left, mid, right = 0, 1, 2

left < right이라 탐색을 계속한다.

cards[mid] "2" < target "3"이기 때문에 left = mid + 1

 

3. left, mid, right = 2, 2, 2

left < right이 아니기 때문에 탐색을 중지하고, right이 target의 lower bound가 된다.

 

 

# NumberCard2.py - LowerBound

def LowerBound(left, right, target):
    while left < right:
        mid = int((left + right)/2)
        # print ("{0} {1} {2} {3}".format(left, mid, right, target))
        if cards[mid] < target:
            left = mid + 1
        elif target <= cards[mid]:
            right = mid

    return right

 

 

 

 

2) Upper Bound

Upper Bound는 정렬된 리스트에서 찾는 값을 초과하는 값이 처음 나오는 위치다.

cards = [1, 2, 3, 3, 3, 5]에서 3의 Upper Bound는 index 5가 되고, 4를 찾는다면 Upper Bound는 index 5가 된다.

 

Lower Bound를 찾을 때와 반대로 mid <= target일 때 left = mid + 1로 찾아가야 한다.

 

cards = [1, 2, 3, 3, 3, 5], target = 3

1. left, mid, right = 0, 2, 5

cards[mid] "3" <= target "3"이므로 left = 2 + 1

 

2. left, mid, right = 3, 4, 5

cards[mid] "3" <= target "3"이므로 left = 3 + 1

 

3. left, mid, right = 4, 4, 5

cards[mid] "3" <= target "3"이므로 left = 4 + 1

 

4. left, mid, right = 5, 5, 5

left < right이 아니기 때문에 탐색을 종료하고, Upper Bound는 5가 된다.

 

 

# NumberCard2.py - UpperBound

def UpperBound(left, right, target):
    while left < right:
        mid = int((left + right)/2)
        # print ("{0} {1} {2} {3}".format(left, mid, right, target))
        if cards[mid] <= target:
            left = mid + 1
        elif target < cards[mid]:
            right = mid
        
    return right

 

 

 

 

문제로 돌아가서..

target의 갯수는 Upper Bound - Lower Bound로 구한다.

 

# NumberCard2.py - main

N = int(input())
strCards = input()

cards = [int(i) for i in strCards.split(' ')]
cards.sort()

M = int(input())
strGuesses = input()

guesses = [int(i) for i in strGuesses.split(' ')]

for i in guesses:
    print ((UpperBound(0, N, int(i))) - LowerBound(0, N, int(i)), end = " ")

 

 

* 주의할 점) 리스트의 모든 원소가 target보다 작을 경우 마지막 원소 다음 index를 반환하기 위해 최초의 right은 리스트의 가장 마지막 원소 + 1이어야한다.

 

 

 

결과)

* Python3로는 시간초과 문제를 해결할 수 없어 PyPy3로 돌렸다.