백준 18870 좌표 압축 - 정렬

18870번: 좌표 압축 (acmicpc.net)

18870번: 좌표 압축

N = int(input())
X = list(map(int, input().split()))
lst = list(set(X.copy()))
lst.sort()
x = []
dic = {lst[i]: i for i in range(len(lst))}
for i in range(len(X)):
    x.append(str(dic[X[i]]))
print(" ".join(x))

뭔가 걍 인덱싱하는 문제라 간단하겠지~ 했는데 헛짓거리하다 오래걸린 ... . .......

내 생각은 for문을 이중으로 돌리면서 지나왔단 값보다 크면 그값에 +1을 하고 그런식으로 하면 될거라 생각했다.

하지만 그렇게 되면 같은 값인데도 계속 커져서 제대로 순위가 매겨지지 않았다.

처음에는 set으로 우선순위를 ..정해서 해야되나 했는데 그렇게하는게 맞긴 맞았지만 list로 바꾸지 않아서 인덱스 참조를 못했다.

그렇다고 계속 max,min값을 변화시켜? 너무 번거로와서 머리 터졋다.

list를 하나 더 복사하고싶은데 깊은복사가 돼서 sort할수도 없었다.

정답은

1.복사는 list.copy()로

2.set으로 전환시킨 뒤에 list로 전환

3.copy된 새로운 list의 인덱스를 참조하면서 해당하는 값이 있으면 이를 출력!!

 

이런 간단한 방법으로 이뤄지는데..

잘 되는데 또!! 또! 또간초과가 되는것임! ;; 

이유인 즉슨! list.index(값)을 하면 처음부터 쫙 훑기 때문에 O(N)의 시간복잡도를 가져서 느리게 된다는 것이다.

따라서 처음으로 dictionary를 만들어봤다. 만드는 방법은

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

이런 식으로 { : }하면 됨!

이렇게하면 잘 된다.ㅎ