18870번 좌표 압출

문제 출처 :https://www.acmicpc.net/problem/18870

너무나 파이썬스러운 깔끔한 풀이로 공부하고자 포스팅.

O(n^2)의 시간복잡도로 무조건 해결가능한 문제로 결국 문제의 핵심은 어떻게 실행 시간을 단축시킬 것인가?

나름 파이썬의 enumerate를 사용해서 index를 동시에 보관하고 정렬의 시간복잡도,O(nlogn), 리스트 조회, O(1), 로 해결가능해 보였다.

고수분의 코드를 분석하면 a에서 중복을 제거하기 위해 set형식으로 바꿔 b에 정렬저장한다. 이후 이 b에 대해 다시 dictionary형식으로 바꿔 c에 저장한다. 이렇게 되면 c에는 "값:작은 수의 개수" 형식으로 저장되게 된다. 이후 다시 a의 element들을 차례대로 c에 key로 대입해 작은 수의 개수를 value로 출력한다.

파이썬의 자료구조를 활용한 명쾌한 풀이

set : 중복제거
dictionary : { key : value }

+) set은 index가 존재하지 않지만 sorted(set) 적용 가능