[BAEKJOON] 좌표 압축 / 19970 / Python

 

 

백준 문제 링크

풀이 Github 링크

 

문제

수직선 위에 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
• 10 ≤ X ≤ 10i
• 9
• 9

 

 

예제 입력 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

 

 

 

---

 

풀이

나의 풀이

 

시간 초과..

import sys

input()
num_list = list(map(int, sys.stdin.readline().split()))

answer = []

new_list = sorted(list(set(num_list)))

for i in num_list:
    answer.append(new_list.index(i))

for a in answer:
    print(a, end=' ')

리스트의 중복을 없애고, 정렬을 하는 과정에서 O(n)이라는 시간 복잡도가 쓰이고, 해당 리스트의 인덱스 값을 찾기위해 index 함수를 사용하는 과정에서 O(n)이라는 시간이 쓰여 결국엔 O(n*2)의 시간 복잡도가 쓰이게 된다. 이를 해결하기 위해 dict를 사용해보았다.

 

 

정답

import sys

input()
num_list = list(map(int, sys.stdin.readline().split()))

answer = []

num_dict = {}

for index, data in enumerate(sorted(list(set(num_list)))):
    num_dict[data] = index

for i in num_list:
    answer.append(num_dict[i])

for a in answer:
    print(a, end=' ')

dict 에 인덱스 값을 넣어 시간을 줄여주었다.

 

 

 

다른 사람의 풀이

import sys

N = int(input())
inputList = list(map(int,sys.stdin.readline().rstrip().split()))

sortedList = sorted(list(set(inputList)))
dictList = dict(zip(sortedList,list(range(len(sortedList)))))

for x in inputList:
    print(dictList[x])