[백준] 10815번, 숫자 카드

 

 

 

 

 

 

 

접근법

- 이분 탐색에 대해서 개념을 확실히 짚고 넘어가고 싶어 이 문제를 골랐다. 하지만 처음에 직관적으로 본 방법은 이분 탐색은 아니었다.

 

- 첫 번째로 푼 방법은, 그냥 N_list와 M_list에 각각 입력을 받아 넣어주고,  M_list를 for문을 돌리면서 M_list의 원소가 N_list에 있는지를 in을 통해서 검사하는 방법이었다.

 

- 당연하게도 M_list의 크기(for i in M_list) x N_list의 크기(i in N_list)로 시간 복잡도가 커져서 시간 초과가 발생하였다.

 

- 그래서 두 번째로 푼 방법은, 배열의 값을 미리 계산하고 인덱스를 통해서 결과값에 접근하는 방식이다. l이라는 배열에 [False] * 20000001(총 가능한 숫자의 가짓수)를 넣어준다. N_list를 for문을 돌면서 l[10000000 + i]의 값을 True로 바꿔준다.

(10000000을 더해준 이유는 숫자의 범위가 -10,000,000부터이기 때문에, 이를 배열의 인덱스로 쓸 수 없어서이다. ) 

 

- 그 후에 M_list를 따로 for문을 돌면서 l[10000000 + i]가 True면 1을 False면 0을 출력하여 풀었다.

 

- 이 경우에 시간 복잡도는 M_list + N_list로 아까보다는 많이 완화되었으나, 필요 이상으로 메모리를 낭비하게 되었다.

 

- 마지막 방법으로는 문제의 카테고리처럼 이분 탐색을 이용하여 풀었다. Binary_search라는 함수의 매개변수로 타깃 값을 저장하고 있는 value, 배열 array, 시작점 start, 끝점 end를 받는다. start > end인 상황이 오면 타깃 한 값이 없는 것이기 때문에 0을 리턴해준다. 

 

- 시작 시 들어오는 값은 0, len(N_list)이다. 이것을 mid = (start + end) // 2로 설정하고 array[mid] == value인 경우 타깃 한 값이 배열 안에 있는 것이기 때문에 1을 return 한다. 그러나 value가 큰 경우 start를 mid + 1로 설정하여 절반으로 나눠진 두 영역 중 큰 영역에서 다시 Binary_search를 하게 한다. 반대로 value가 중간값보다 작은 경우 end를 mid - 1로 설정하여 작은 영역에서 다시 Binary_search를 수행한다.

 

 

 

 

 

 

풀이 (방법 2)

l = [False] * 20000001

N = int(input())
N_list = list(map(int, input().split()))
M = int(input())
M_list = list(map(int, input().split()))

for i in N_list :
    l[i + 10000000] = True

for j in M_list :
    if l[j + 10000000] :
        print(1, end=" ")
    else :
        print(0, end=" ")

 

결과 (풀이 2)

 

 

 

 

 

풀이 (방법 3)

def Binary_search(value, array, start, end) :
    if start > end :
        return 0

    mid = (start + end) // 2

    if array[mid] == value :
        return 1
    elif array[mid] < value :
        start = mid + 1
    else :
        end = mid - 1

    return Binary_search(value, array, start, end)

N = int(input())
N_list = list(map(int, input().split()))
M = int(input())
M_list = list(map(int, input().split()))

N_list = sorted(N_list)

answer = list()

for i in M_list :
    answer.append(Binary_search(i, N_list, 0, len(N_list) - 1))

print(" ".join(map(str, answer)))

 

결과 (풀이 3)

 

 

 

이분 탐색을 사용한 경우 메모리의 낭비는 크지 않았지만, 이분 탐색의 특성 상 미리 배열을 sort를 해놔야 하기 때문에 시간이 상대적으로 오래 걸린 것을 확인할 수 있다.