배열리스트 문제 5번 질문입니다.

Question

안녕하세요!~ 배열리스트 문제 5번 <중복 제거> 질문입니다. for i in range(1, len(nums)): 이후 조건문에서 선생님께서 알려주신 직전항과의 값이 같은지 비교하는거 말고, if nums[i] not in answer: answer.appendleft(nums[i])   이런식으로 코드를 작성하게 되면 시간 효율에서 문제가 생기게 될까요? 아무래도 nums 크기마다 한 번씩 answer 전체를 탐색해야해서 효율이 더 떨어질 것 같긴한데 궁금해서 질문드려봅니다!   감사합니다.

communityai8509 · Answer

안녕하세요, 인프런 AI 인턴입니다. pppcent님, 문의하신 내용에 답변드리겠습니다. 리스트 nums 에서 중복 요소를 제거하는 문제에서 if nums[i] not in answer: 를 사용한 코드는 실제로 시간 효율성에서 문제가 생길 수 있습니다. Python에서 not in 연산자를 사용할 때, 리스트 answer 의 모든 요소를 처음부터 끝까지 확인해야 하기 때문에, answer 리스트의 길이가 길어질수록 시간 복잡도가 증가합니다. 이 연산은 answer 리스트의 길이 n 에 대해 최악의 경우 O(n)의 시간 복잡도를 가집니다. 따라서 nums 리스트를 전부 확인하는 완전 탐색 과정에서 이런 식으로 중복 검사를 할 경우, 전체 시간 복잡도는 O(n^2)이 될 수 있습니다. 리스트의 크기가 큰 경우 매우 비효율적인 연산이 됩니다. 선생님이 제안하신 방법은, 이미 정렬되어 있다는 가정 하에 직전 항과 현재 항만을 비교하여 O(n) 시간 내에 중복을 제거할 수 있는 효율적인 방법입니다. 이후에 다루어질 내용들에서 데이터의 크기가 크거나 효율성을 요구하는 문제들이 많기 때문에, 이러한 효율적인 접근 방법을 습득하면 이후 코딩 테스트나 알고리즘 문제를 해결할 때 큰 도움이 될 것입니다. 도움이 되셨기를 바랍니다. 좋은 하루 되세요!