-
sort→set 하는 것과 set→sort 하는 것의 차이가 있을까?Coding Test/Data Structure & Algorithm 2022. 7. 4. 21:16
Problem
코딩테스트 문제를 풀다가 sort 를 하고 set 을 했을 때와 set 을 하고 sort 를 했을 때의 결과가 다른 것을 알게 되었다.
Searching
set 은 순서를 고려하지 않고 중복을 제거해주는 함수이다. 순서를 고려하지 않는다는 것이 단순히 정렬되어 있지 않아도 사용할 수 있다는 것으로 이해했던 나는 크나큰 오해를 하고 있음을 파이썬 레퍼런스를 읽어보고 깨달았다.
https://docs.python.org/2/library/sets.html8.7. sets — Unordered collections of unique elements — Python 2.7.18 documentation
8.7. sets — Unordered collections of unique elements Deprecated since version 2.6: The built-in set/frozenset types replace this module. The sets module provides classes for constructing and manipulating unordered collections of unique elements. Common u
docs.python.org
그 이유는 아래와 같다.sets support x in set, len(set), and for x in set. Being an unordered collection, sets do not record element position or order of insertion. Accordingly, sets do not support indexing, slicing, or other sequence-like behavior.
set 은 집합이기 때문에 요소의 위치나 삽입 순서를 기록하지 않는다고 한다. dictionary(다른 말로는 map)처럼 index가 없다는 뜻이다. 즉, sort 를 사용했을 때에는 index를 가지고 있었으나 set 으로 변환되면서 위치 데이터가 날아갔다는 것을 의미한다.
Result
결론! 차이가 있다!!
Optional
그렇다면 set 은 list 와 비교했을 때 시간복잡도가 어떻게 될까? 이를 알아보기 위해 파이썬 레퍼런스를 뒤져보았다.
https://docs.python.org/3.8/library/stdtypes.html#set-types-set-frozensetBuilt-in Types — Python 3.8.13 documentation
The following sections describe the standard types that are built into the interpreter. The principal built-in types are numerics, sequences, mappings, classes, instances and exceptions. Some collection classes are mutable. The methods that add, subtract,
docs.python.org
A set object is an unordered collection of distinct hashable objects. Common uses include membership testing, removing duplicates from a sequence, and computing mathematical operations such as intersection, union, difference, and symmetric difference.
파이썬에서 set은 해싱이 가능(hashable)하다고 나와있다. 그러므로 시간 복잡도는 O(1)이다. 해시충돌이 일어난다고 했을 때의 시간복잡도는 최악의 상황이라봐야 O(n)이 나온다. 반면, list는 선형 탐색을 했을 시에 O(n)이 나오게 된다.
해시에 관해서는 자세히 설명을 해준 블로그가 있으므로 링크 첨부합니다.
https://d2.naver.com/helloworld/831311