파이썬Python | 리스트(list) 중복 제거

 

최근 백준(https://www.acmicpc.net/)에서 알고리즘 공부를 하고 있는데, 언어를 파이썬으로 정하는 바람에 모르는 부분이 많아 매우 헤매고 있는 중입니다..🥲 며칠 전 리스트의 중복 제거 문제를 봤는데, 기존하던 대로 당연히 for 반복문을 이용해 요소를 순회하려 했습니다. 그러나 정말 여러 가지 방법이 있다는 것을 알고 굉장히 신기했습니다.

 

 

 

---

집합 자료형 SET() 이용하기

집합 자료형의 특징 중 하나가 중복이 없다는 점입니다. 이 특징을 이용하면 쉽게 중복이 없는 set 타입으로 변경됩니다. 제가 본 문제처럼 중복이 안된 수의 개수를 알고 싶다면 여기서 len() 함수만 이용하면 됩니다.

리스트(list)에서 집합(set)으로

그러나 만약 기존 순서를 유지한 채 중복 제거를 하고 싶다면 순서가 무작위로 바뀌는 SET을 사용하면 안됩니다. 

 

 

 

---

딕셔너리(Dictionary) 이용하기

파이썬에는 딕셔너리라는 대응 관계 자료형이 있습니다. 흔히 다른 언어에서도 볼 수 있는 Key-Value 형식이며 해시(Hash)도 이러한 대응 관계를 나타내고 있습니다. 

이 딕셔너리는 위에서 본 SET()과 마찬가지로 Key가 중복이 없다는 점입니다. 당연하게도 중복되는 Key값이 있다면, 그에 해당하는 Value 중 어느 것을 가져와야 할지 혼란이 생기기 때문에 그렇습니다. 이 특징을 이용하면 기존 리스트의 순서를 유지하며 중복을 제거할 수 있습니다.

리스트-딕셔너리-리스트 변환

처음 중복된 수가 들어있는 리스트 arr를 만들어주고, type이 list임을 확인해봤습니다. 그런 다음 dict.fromkeys()를 이용하여 리스트를 딕셔너리로 변환했는데,  두 번째 인자로 Value를 줄 수 있지만 아무것도 쓰지 않으면 Value는 None이 됩니다. 딕셔너리로 변환된 arr를 확인해보니 중복된 수가 사라진 것을 볼 수 있습니다. 이제 다시 list()로 리스트 변환을 해주면 기존 순서는 유지하며 중복된 수만 사라지게 됩니다.

 

 

 

---

for 반복문 사용하기

파이썬에는 not in 이라는 좋은 기능이 있습니다. 기존 리스트인 arr과 새로 중복 없는 값을 저장할 temp를 만들어주고, for문과 if문을 통해 temp에 값을 추가해줍니다. 이 방법으로 할 경우 시간 복잡도가 O(N)으로 

not in 사용해보기

if문에서 not in을 사용하면 현재 i 값이 temp에 없을 경우만 append됩니다. 참고로 궁금해서 찾아본 list의 append의 시간 복잡도는 O(1)였습니다.

 

 

 

---

번외

아래 코드는 맨 처음 언급한 제가 한 for문입니다.. 일단 공부없이 부딪혀보자!라는 객기로 기본적인 문법 공부도 안했더니 not in의 존재조차 몰랐습니다.😂 중첩 for문을 사용해 임시 리스트 temp에 없는 숫자만 append로 추가할 수 있도록 했습니다.. 결과는 어떻게 잘 나왔지만 위의 not in을 사용한 for 사용법과 달리, 이 방법은 시간 복잡도가 O(n²)라서 웬만하면 집합이나 딕셔너리를 사용하려 합니다.