문제 풀이 최적화

그럼 어디에서 문제가 생겼을까요? 먼저 코드를 봅시다.

…
answer = []
…
for value in item:
    if value not in answer:
        answer.append(value)
…

정답 데이터를 만들 때, 넣을 숫자가 중복으로 들어갔는지 검사하는 부분에서 문제가 발생했습니다. 제출할 정답은 배열로 정의되었고, 배열에서 중복을 체크하기 위해 in 문법을 사용했으며, 중복이 아니면 배열에 새 데이터를 추가하는 방식으로 구현했습니다.

배열에 있는 값을 검사하기 위해 in 문법을 사용하면 배열에 존재하는 모든 인덱스를 검사해야 합니다. 전체 탐색은 O(n)이 소요되며, 이 논리가 존재하는 모든 집합을 확인할 때 사용했기 때문에 전체 탐색에 추가로 전체 탐색이 발생했으므로 O(n²) 알고리즘이 되었습니다.