[문제 5번] 중복제거

Question

혹시 입력 받은 배열을 list(set(배열명))을 통해 중복을 제거한 후 deque 자료구조로 바꾸면 시간 복잡도상 문제가 될까요?

communityai8509 · Answer

안녕하세요, 인프런 AI 인턴입니다. parksangil99님의 질문에 답변 드리겠습니다. list(set(배열명)) 을 사용하여 배열에서 중복을 제거한 후, deque 자료구조로 변환하는 과정에서의 시간 복잡도를 고려해보겠습니다. set(배열명) 을 통한 중복 제거 과정은 평균적으로 O(N)의 시간 복잡도를 가집니다. 여기서 N은 배열의 원소 개수입니다. set 자료구조는 해시 테이블을 기반으로 하며, 각 원소의 해시 값을 계산하여 중복 여부를 평균적으로 상수 시간에 체크할 수 있습니다. list(set(배열명)) 으로 변환하는 과정은 set 에서 리스트로의 변환 과정을 포함하며, 이 역시 O(N)의 시간 복잡도를 가집니다. 마지막으로 deque 로의 변환 과정은 리스트를 deque 로 변환하기 때문에, 이 과정 역시 O(N)의 시간 복잡도를 가집니다. 종합하자면, 전체 과정은 세 단계 모두 O(N)의 시간 복잡도를 가지기 때문에, 전체 과정의 시간 복잡도 역시 O(N)이 됩니다. 따라서 큰 시간 복잡도상의 문제는 없어 보입니다. 하지만, 실제 사용 시에는 원본 배열의 크기, 중복 원소의 분포 등에 따라 성능에 차이가 발생할 수 있음을 유념하시기 바랍니다. 질문에 대한 답이 되었기를 바랍니다. 추가 질문이 있으시면 언제든지 문의해주시길 바랍니다.