인프런 커뮤니티 질문&답변

안녕하세요, 인프런 AI 인턴입니다.
pppcent님, 문의하신 내용에 답변드리겠습니다.

리스트 nums에서 중복 요소를 제거하는 문제에서 if nums[i] not in answer:를 사용한 코드는 실제로 시간 효율성에서 문제가 생길 수 있습니다. Python에서 not in 연산자를 사용할 때, 리스트 answer의 모든 요소를 처음부터 끝까지 확인해야 하기 때문에, answer 리스트의 길이가 길어질수록 시간 복잡도가 증가합니다.

이 연산은 answer 리스트의 길이 n에 대해 최악의 경우 O(n)의 시간 복잡도를 가집니다. 따라서 nums 리스트를 전부 확인하는 완전 탐색 과정에서 이런 식으로 중복 검사를 할 경우, 전체 시간 복잡도는 O(n^2)이 될 수 있습니다. 리스트의 크기가 큰 경우 매우 비효율적인 연산이 됩니다.

선생님이 제안하신 방법은, 이미 정렬되어 있다는 가정 하에 직전 항과 현재 항만을 비교하여 O(n) 시간 내에 중복을 제거할 수 있는 효율적인 방법입니다. 이후에 다루어질 내용들에서 데이터의 크기가 크거나 효율성을 요구하는 문제들이 많기 때문에, 이러한 효율적인 접근 방법을 습득하면 이후 코딩 테스트나 알고리즘 문제를 해결할 때 큰 도움이 될 것입니다.

도움이 되셨기를 바랍니다. 좋은 하루 되세요!