백준 18870 좌표 압축 python3

https://www.acmicpc.net/problem/18870

18870번: 좌표 압축

자기 전에 간단한 문제를 하나 풀고 자겠습니다.

 

문제는 주어진 입력이 X1, X2, .., Xn 일 때 Xi 보다 작은 값이 몇 개인지 구하는 문제입니다.

처음 입력에 대해 중복을 제거한 오름차순 정렬 후 해당 값의 index를 구해주면 됩니다.

 

예제를 예를 들면 입력이 2 4 -10 4 -9 일 때

-10 -9 2 4 로 중복 제거 오름차순 => -10의 index = 0 ,-9의 index = 1, 2의 index = 2, 4의 index = 3 임을 알 수 있고 이는 답입니다.

 

코드는 다음과 같습니다.

처음에 index 함수를 이용해 그냥 구하려했는데 시간초과가 났습니다. index 찾는데 정렬된 상황에서 이분 탐색으로 찾아도 100만개면 O(100만 * log100만) 이고 dict로 찾는 건 O(1) 이므로 O(100만) 입니다. 그래서 dict로 변환 후 다시 검색을 합니다.