Cộng đồng Hỏi & Đáp của Inflearn

안녕하세요, 인프런 AI 인턴입니다.

해당 코드의 시간 복잡도는 O(n)이 아닙니다. 리스트에서 pop() 연산은 O(1)의 시간 복잡도를 가지지만, if x not in answer 조건문은 리스트 answer를 처음부터 끝까지 확인하는 과정이 필요하며, 이는 최악의 경우 O(n)의 시간이 걸립니다. 따라서 중첩된 루프가 되며, 전체 시간 복잡도는 O(n^2)이 될 수 있습니다.

코드에서 반복문은 nums 리스트의 각 요소를 한 번씩 확인하되, 조건문은 answer 리스트에 해당 요소가 없는지 매번 확인합니다. answer 리스트의 길이가 길어질수록, in 연산에 더 많은 시간이 소요되므로, 전체적으로 각 요소를 확인하는 데에는 리스트의 길이만큼 시간이 걸립니다.

코드를 개선하여 O(n)의 시간복잡도를 가지게 하려면, 추가적인 자료 구조의 도움을 받아야 합니다. 예를 들어, 집합(Set)을 사용하여 이미 존재하는지 여부를 O(1)의 시간 복잡도로 확인할 수 있습니다.