시간 복잡도 생각 with 백준 10815 숫자카드

문제는 간단하다 내가 소유하고 있는 카드들과

존재여부를 확인하고 싶은 카드들을 입력받는다.

범위를 보면 -10000000~10000000 로 int로도 처리 된다. 

나는 처음에 생각한게
먼저 단순히 target을 python의 in연산자로 찾으면 O(N)의 시간 복잡도로 찾아지게 되므로 시간초과가 뜰 것같았다.
그래서 리스트에서 값을 찾을 때 O(logN)의 속도로 찾을 수 있는 이분탐색을 사용해서 찾을려고 했다.
근데 멍청하게 O(logN)에서 찾은 애들은 remove를 시켜주겠다는 생각을 했다.
list에서 remove를 해주는 것이 더빠르다고 생각해서 remove를 해주었다.
하지만 일반 적인 생각말고 시간복잡되 관점에서 remove는 찾는 것과 마찬가지로 O(N) 시간복잡도를 가진다. 
그래서 O(N logN) 로 시간복잡도가 되어 시간초과가 났다.
remove를 할거면 index로 접근해서 O(1)로 처리했어야 했다. 
그래도 이번 기회를 통해 시간복잡도를 좀 더 생각하면서 코테를 준비할 수 있는 기회가 되었다.

def main():
    n = int(input())
    owns = list(map(int, input().split()))
    t = int(input())
    targets = list(map(int, input().split()))
    owns.sort()
    print(*bin_search(owns, targets))


def bin_search(owns: list, targets: list) -> list:
    answer = [] # 이분 탐색으로 시간복잡도 O(log N) remove를 포함시키면 시간복잡도 O(N logN)
    for target in targets:
        start = 0
        last = len(owns) - 1
        check = True
        while start <= last:
            middle = (start + last) // 2

            if owns[middle] == target:
                answer.append(1)
                #owns.remove(target) remove 연산 O(N)으로 시간 복잡도  증가함.
                check = False
                break
            elif owns[middle] > target:
                last = middle - 1
            else:
                start = middle + 1
        if check:
            answer.append(0)
    return answer


if __name__ == "__main__":
    main()

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

10815번: 숫자 카드