Set과 List에서 중복을 제거하는 방법 비교

List 사용

삽입

• List의 add 메서드를 사용하여 원소를 삽입하는데 O($1$)의 시간 복잡도가 걸린다
  그러나, 중복 제거를 위해서는 contains 메서드를 사용해야 하므로 O($n$)의 시간 복잡도가 추가로 필요하다

중복 제거

• List에서 각 원소를 확인하면서 contains() 메서드로 중복 여부를 체크하면 O($n^2$)의 시간 복잡도가 발생한다.

HashSet 사용

삽입

• HashSet에서 add 메서드는 내부적으로 해시 테이블을 사용하므로 원소의 존재 여부를 확인하는데 평균적으로 O($1$)의 시간 복잡도가 걸린다.
  그러나, 해시 충돌이 발생할 경우 O($n$)까지 걸릴 수 있지만, 실제 실용적인 환경에서는 거의 O($1$)에 가깝게 동작한다.

중복 제거

• HashSet은 삽입 과정에서 자동으로 중복을 제거하므로 별도의 중복 제거 작업이 필요하지 않습니다.

총 시간 복잡도

List: 삽입 + 중복 제거 = O($1$) + O($n^2$) = O($n^2$)
HashSet: 삽입 + 중복 제거 = O($1$) + O($1$) = O($1$)