[알고리즘 TIL] 2776. 암기왕

 

문제

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

설명

단순히 리스트에 Target 원소가 포함되어있는지 여부를 파악하는 문제이다. 문제를 읽고, 파이썬이 제공하는 sort 와 in 함수를 사용하면 정답을 낼 수 있는 문제이다. 하지만 고려한 것은 시간 제한이 2초이고, N와 M이 각각 1,000,000 이기 때문에 파이썬이 제공하는 함수의 시간복잡도를 파악하고, 이를 극복할 수 있는 방법을 알아내는 게 관건이었다.

 

• 파이썬이 제공하는 sort 함수의 시간복잡도는 O(NlogN)으로 직접 정렬을 구현하는 것보다 파이썬이 제공하는 함수를 사용하여 정렬하자.
• 파이썬이 제공하는 in 함수의 시간복잡도는 O(N)으로, 직접 이진탐색을 구현하여 O(logN)의 시간복잡도로 해결해야겠다.

구현

def binary_search(arr, target):
    def bs(start,end):
        if start>end: return False
        mid = (start+end)//2
        if arr[mid] == target: return True
        elif arr[mid] < target: return bs(mid+1,end) #상위 호출에서도 반환해주어야함!
        elif arr[mid] > target: return bs(start,mid-1)
    return bs(0,len(arr)-1)

T = int(input())

for _ in range(T):
    N = int(input())
    memo1 = list(map(int,input().split(" ")))
    M = int(input())
    memo2 = list(map(int,input().split(" ")))
    memo1.sort()

    for num in memo2:
        # 이진 탐색
        if binary_search(memo1,num): print("1")
        else: print("0")

새로 알게된 점

처음에 재귀함수를 다음과 같이 구현했다.

if start>end: return False
        mid = (start+end)//2
        if arr[mid] == target: return True
        elif arr[mid] < target: bs(mid+1,end) #상위 호출에서도 반환해주어야함!
        elif arr[mid] > target: bs(start,mid-1)

하지만 True 값이 올바르게 반환되지 않아 이유가 무엇인지 살펴보니, bs 함수에서 True나 False 값을 재귀 호출에서 반환받더라도 이를 상위 호출에서 반환하지 않고 있기 때문이었다. 즉, bs 내부에서 조건에 따라 True를 반환할지라도, 이 반환값은 호출한 곳으로 전달되지 않고 있었다.

 

재귀 함수를 구현할 때, 상위 호출에도 전달될 수 있도록 return을 빼먹지 말아야겠다.