★[백준/python] 18870 좌표압축: dictionary/ list.index(i) , dictionary[i]의 시간복잡도

문제

---

수직선 위에 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을 공백 한 칸으로 구분해서 출력한다.

 

 

제한

---

• 1 ≤ N ≤ 1,000,000
• -109 ≤ Xi ≤ 109

예제 입력 1

---

 

5 2 4 -10 4 -9

 

예제 출력 1

---

 

2 3 0 3 1

 

예제 입력 2

---

 

6 1000 999 1000 999 1000 999

 

예제 출력 2

---

 

1 0 1 0 1 0

 

 

 

---

처음에는, 일단 리스트에 입력 받은 후, 반복문을 돌아가며 더 작은 값이 있을 경우 카운트갯수를 담는 리스트에 증가시키는 방식으로 하려고 했었다.

구현도 잘 안되고 더 좋은 방식이 없을까 고민하다가,

 

 

#인덱스번호대로 출력. a[0]=2라면, 2는 0을 출력

#근데 이렇게 하면 인덱스번호가 겹칠 수 있으니까 반대로

#a[2]=0 형태로 할거임.

#중복되는 값을 제거(set)해주었으니 위의 형태는 겹칠 일 없음.

# 따라서 dict의 key value를 이용.

import sys

n=int(input())

arr=list(map(int, sys.stdin.readline().strip().split()))
arr2=list(set(arr))
arr2.sort()

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

for i in range(len(arr)):
  print(dic[arr[i]], end=' ')
  

 

 

처음엔 dic를 딕셔너리가 아니라 리스트로 사용하니 오류가 떴다.

그리고 주의할 점은 마지막 출력부에서 원래의 입력 받은 배열대로 출력을 해줘야하기때문에 원래 arr가 필요하다. 그래서 arr를 갱신하지말고 새로운 변수를 추가하여 풀어야한다.

 

 

import sys

input = sys.stdin.readline

n = int(input())
arr = list(map(int, input().split()))

arr2 = sorted(list(set(arr)))

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

 

위 코드는 같은 방식이지만 딕셔너리를 사용하지 않았다. 시간은 더 오래 걸린다. 왜냐하면 list.index(i) 형태는 시간 복잡도 O(N)를 가지고 있다.

딕셔너리를 이용하면 dict[i]의 형태로 시간복잡도 O(1)을 만든다.