[알고리즘] 백준1920 (파이썬)

코테를 위한 알고리즘 연습을 하면 점점 시간복잡도에 대한 생각을 하게 된다. 왜냐하면 분명 답은 맞았는데 시간초과로 뜨기 때문이다. 1920을 풀면서 파이썬의 시간복잡도에 대한 주의점? 이나 팁에 대해 간단히 작성한다.

'실버 4'이지만 낮은 정답 비율을 갖는다.
이유로는 처음 접근법을 그냥 완전탐색처럼 하는 경우와 이분탐색을 했지만 하는 과정에서 시간복잡도가 늘어나는 경우가 있다.

우선 첫 번째 이유를 보자
나도 처음엔

if i in list_A:
	print(1)

과 같은 방식으로 풀었고 시간초과가 났다.
이 문제의 요지가 이분탐색이기 때문이다.
근데 이 방법으로도 풀 수 있는 방법이 있다.
숫자의 배열을 list로 담는게 아니라 set으로 담는 경우이다.
set은 index를 찾는데 O(1)의 시간이 걸린다고 한다. 이 문제와 같은 경우엔 중복이 되는 경우가 없고 순서가 상관없기 때문에 set을 이용하여 푸는 방법이 있을 것이다.

두 번째 이유를 보자
이 문제는 이분탐색으로 푸는거니까 그래도 이분탐색으로 풀어봐야지

import sys
A=int(sys.stdin.readline())
B=list(sorted(map(int,sys.stdin.readline().split())))
C=int(sys.stdin.readline())
D=list(map(int,sys.stdin.readline().split()))

def binary(B,value):
    n=len(B)
    if B[-1]<value or B[0]>value:
        return 0
    if n == 1:   #리스트가 1개일 때
        if B[0] == value:
            return 1
        else:
            return 0
    if B[n//2] == value: #리스트 가운데 값과 비교
        return 1
    if B[n//2] > value: # 큰지 작은지에 따라 재귀
        return binary(B[:(n//2)],value)
    if B[n//2] < value:
        return binary(B[(n//2)+1:],value)


for i in D:
    print(binary(B,i))

그런데 희한하게 계속 시간 초과가 뜬다.
알고보니 파이썬에서 list slicing을 할 때에 O(n)의 시간복잡도를 가지게 된다. 따라서 binary가 한번 실행될 때마다 시간복잡도가 상승한다.

그러면 어떻게 해야할까?
답은 간단하다 slicing을 하지 않고 시작점과 끝점을 정해서 범위를 지정하면 된다.