백준 18870번 : 좌표 압축(S2)

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

 

문제

수직선 위에 N개의 좌표 X1, X2, ..., XN이 있다. 이 좌표에 좌표 압축을 적용하려고 한다.

Xi를 좌표 압축한 결과 X'i의 값은 Xi > Xj를 만족하는 서로 다른 좌표 Xj의 개수와 같아야 한다.

X1, X2, ..., XN에 좌표 압축을 적용한 결과 X'1, X'2, ..., X'N를 출력해보자.

 

내 코드

import sys

input = sys.stdin.readline

    
def main() :
    n = int(input())
    array = list(map(int, input().rstrip().split()))
    unique_array = list(set(array)) #중복제거

    ans = []
    sorted_array = sorted(unique_array)
    
    dic = {value : idx for idx, value in enumerate(sorted_array)}
    
    for key in array :
        print(dic[key],end=' ')

if __name__ == "__main__" :
    main()

느낀점

1. 딕셔너리를 잘 사용할 줄 알아야한다. (딕셔너리에 너무 무관심했음)

2. 시간 초과를 막기 위한 솔루션들을 많이 알아두자. (알고리즘 효율화)

3. .index 메소드는 별로다. for문 안에 있으면 o(n^2)됨

풀이 시간