백준 18870번. 좌표 압축 (Python / 파이썬)

문제

수직선 위에 N개의 좌표 X1, X2, ..., XN이 있다. 이 좌표에 좌표 압축을 적용하려고 한다.
Xi를 좌표 압축한 결과 X'i의 값은 Xi > Xj를 만족하는 서로 다른 좌표의 개수와 같아야 한다.
X1, X2, ..., XN에 좌표 압축을 적용한 결과 X'1, X'2, ..., X'N를 출력해보자.

입력

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

출력

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

---

문제 풀이

N개의 좌표가 주어졌을 때 좌표 압축을 적용한 결과를 출력하는 문제이다. 

Xi를 좌표 압축한 결과는 Xi > Xj 를 만족하는 서로 다른 좌표의 개수이다. 

 

즉, 나를 제외한 나머지 원소들 중 나보다 더 작은 값의 좌표 개수를 구하면 된다. 

좌표 개수를 구할 때 중복 문제가 발생할 수 있다. 

예를 들어, 1000 999 1000 999 1000 999 과 같이 좌표가 주어졌을 때 

좌표 압축 결과는 1 0 1 0 1 0 이다. 

1000보다 작은 좌표의 개수는 실제로 999 3개이지만 3개의 값이 같으므로 1개가 되는 것이다. 

이러한 중복 문제를 방지하기 위해 주어진 좌표들의 중복을 제거해야 한다. 

중복을 제거하기 위해 set() 함수를 이용하였다. 

 

중복을 제거한 후의 결과는 1000 999이다. 

이때 이 결과를 오름차순으로 정렬하면

999 1000이 되고 이때의 index 값은 구하고자 하는 좌표 압축의 결과가 된다. 

 

따라서, 원래의 주어진 좌표값이 중복을 제거한 후 오름차순으로 정렬한 값에서 몇번째 index인지 

확인하고 그 값을 출력해주면 답을 구할 수 있다. 

하지만 index를 구하려면 모든 좌표 값을 하나씩 확인해야 하므로 시간초과 문제가 발생한다. 

 

시간 초과 문제를 해결하기 위해 dictionary를 이용해주었다. 

좌표 값을 key, index를 value 값으로 저장해주어 해당 값의 index를 바로 출력하도록 해주면

시간 초과 문제를 해결할 수 있다. 

---

My Code 1 - 시간 초과 

import sys 
input = sys.stdin.readline

# 좌표의 개수 
n = int(input())

# 좌표 정보 
array = list(map(int,input().split()))

# 중복 제거 
new_array = list(set(array))
# 오름차순으로 정렬
new_array.sort()

# new_array의 index 값이 좌표 압축의 결과이므로 new_array에서의 index 값을 출력
for i in array:
    num = new_array.index(i)
    print(num, end = ' ')

My Code 2 - 시간 초과 해결 

import sys 
input = sys.stdin.readline

# 좌표의 개수 
n = int(input())

# 좌표 정보 
array = list(map(int,input().split()))

# 중복 제거 
new_array = list(set(array))
# 오름차순으로 정렬
new_array.sort()

# 좌표 값과 new_array에서의 index를 key와 value로 저장
dict = {}
for i in range(len(new_array)):
    dict[new_array[i]] = i 

# dict에 저장된 값 출력
for i in array:
    print(dict[i], end = ' ')