좌표 압축 [73]

좌표 압축

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

문제

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

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

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

첫째 줄에 수의 개수 N과 합을 구해야 하는 횟수 M이 주어진다. 둘째 줄에는 N개의 수가 주어진다.

수는 1,000보다 작거나 같은 자연수이다. 셋째 줄부터 M개의 줄에는 합을 구해야 하는 구간 i와 j가 주어진다.

입력

첫째 줄에 N이 주어진다.

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

출력

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

생각

set을 사용해서 중복을 제거하고 list로 바꾸어서 순서를 정해주면 되겠다!

별 생각 없이 index()함수를 사용하여 숫자마다 정렬한 배열에서 찾아줬는데 시간초과가 떳다. 왜 시간초과 일까 생각해보니 for문을 돌리고 배열에서 값을 찾으면 O(N^2)의 시간복잡도였다.

그래서 시간초과를 해결하기 위해 list(set()).sort()를 한 배열의 원소들을 딕셔너리로 바꾸어

key = 숫자 , value = index값으로 설정하여 원하는 숫자를 O(1)의 시간복잡도로 찾을수 있게 수정하였다.

시간복잡도

O(N^2) -> O(N)

풀이 코드

N = int(input())
arr = []
arr = list(map(int,input().split(" ")))

sortArr = sorted(list(set(arr)))
dictionary = dict()
for index in range(len(sortArr)):
    dictionary[sortArr[index]] = index
for x in arr:
    print(dictionary[x],end=" ")