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

parksangil99님의 프로필 이미지

작성한 질문수

입문자를 위한 코딩테스트 핵심(이론과 문제풀이) [Python]

[문제 5번] 중복 제거

[문제 5번] 중복제거

24.09.06 21:09 작성

·

24

0

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

답변 1

0

인프런 AI 인턴님의 프로필 이미지

2024. 09. 08. 21:11

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

parksangil99님의 질문에 답변 드리겠습니다.

list(set(배열명))을 사용하여 배열에서 중복을 제거한 후, deque 자료구조로 변환하는 과정에서의 시간 복잡도를 고려해보겠습니다.

  1. set(배열명)을 통한 중복 제거 과정은 평균적으로 O(N)의 시간 복잡도를 가집니다. 여기서 N은 배열의 원소 개수입니다. set 자료구조는 해시 테이블을 기반으로 하며, 각 원소의 해시 값을 계산하여 중복 여부를 평균적으로 상수 시간에 체크할 수 있습니다.

  2. list(set(배열명))으로 변환하는 과정은 set에서 리스트로의 변환 과정을 포함하며, 이 역시 O(N)의 시간 복잡도를 가집니다.

  3. 마지막으로 deque로의 변환 과정은 리스트를 deque로 변환하기 때문에, 이 과정 역시 O(N)의 시간 복잡도를 가집니다.

종합하자면, 전체 과정은 세 단계 모두 O(N)의 시간 복잡도를 가지기 때문에, 전체 과정의 시간 복잡도 역시 O(N)이 됩니다. 따라서 큰 시간 복잡도상의 문제는 없어 보입니다. 하지만, 실제 사용 시에는 원본 배열의 크기, 중복 원소의 분포 등에 따라 성능에 차이가 발생할 수 있음을 유념하시기 바랍니다.

질문에 대한 답이 되었기를 바랍니다. 추가 질문이 있으시면 언제든지 문의해주시길 바랍니다.