[백준] 18870번 좌표 압축 - python

코드: 실패(시간 초과)

리스트.index()의 시간 복잡도는 O(n)이다.
따라서 시간 초과로 실패..

코드: 성공

코드 설명

1. N을 입력받는다.
2. 배열의 원소들을 입력받는다. 띄어쓰기로 원소들이 구분되므로 split 함수를 이용하여 구분하고 하나의 arr라는 리스트에 넣어준다.
3. arr 리스트를 set()에 넣어서 list였던 구조를 set으로 변환하고 다시 list로 변환한다. 이때 중복된 원소는 허용하지 않는 set의 특성으로 인해 arr_idx에는 arr에서 중복된 원소가 존재하지 않게 된다.
4. arr_idx를 정렬한다.
5. 딕셔너리에서 키를 arr_idx 각각의 요소로 지정하고 해당 키에 해당하는 idx값을 순서대로 값으로 지정한다.

딕셔너리의 시간 복잡도는 O(1)이다.