백준 18870번 (python) - 좌표 압축

좌표 압축

백준 > 단계별로 풀어보기 > 정렬

문제

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

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

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

입력

첫째 줄에 N이 주어진다.

둘째 줄에는 공백 한 칸으로 구분된 X1, X2, ..., XN이 주어진다.

출력

첫째 줄에 X'1, X'2, ..., X'N을 공백 한 칸으로 구분해서 출력한다.

풀이

import sys

N = int(sys.stdin.readline())

array = list(map(int,sys.stdin.readline().split()))
result = sorted(list(set(array)))

dic = {result[i] : i for i in range(len(result))}

for i in array:
    print(dic[i], end=" ")

지금까지 푼 문제들 중에 가장 어려운 문제같다.

복잡한건 없는데, 생각하는게 어려웠다.

array에 배열을 저장하고 나서, 중복을 제거한 후 정렬을한 값을 새 배열에 저장한다.

새 배열의 인덱스는 곧 좌표 압축의 결과와 같다.

중복을 제거한 후 오름차순으로 정렬했으니, 0번 인덱스라면 가장 작으니 자기보다 작은 값은 없을 것이다. 그러므로 0이다.

마찬가지로 1,2,3 늘어갈수록 자기보다 작은 값이 많아지는것이다.

근데, 이대로 index메소드나 그런 식으로 for문을 통해 출력하면 시간초과가 뜬다.

for i in arr:
    print(arr2.index(i), end = ' ')

처음에는 이런식으로 출력했다.

dictionary자료형을 통해 표현해야 시간초과가 발생하지 않는다.

위의 경우에는 O(n) 이지만, dictionary를 통해 표현하면 O(1)이다.

{새로만든 배열의 값 : 그 값의 인덱스} 형태로 저장한 후, 새로만든배열[원래 배열값]하면 새로만든배열에서의 원래 배열의 값을 key값으로 사용해, 인덱스값을 가져올 수 있다.