[백준 18870번] 좌표 압축(파이썬)

문제

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

 

예제 입력

입력 1
5
2 4 -10 4 -9

입력 2
6
1000 999 1000 999 1000 999

예제 출력

출력 1
2 3 0 3 1

출력 2
1 0 1 0 1 0

 

---

 

풀이

이 문제는 리스트 안에서의 크기 순서를 출력하면 됩니다. (단, 좌표는 서로 다른 좌표만 순서 포함)

예를 들면 리스트가 [2, 4, -10, 4, -9] 이렇게 주어지면
일단 중복을 제거 하면 [2, 4, -10, -9] 이고,
2 > Xj → 리스트 안에 2보다 작은 서로 다른 숫자는 (-10, -9) 2개가 있으므로 2는 2을 출력
4 > Xj → 리스트 안에 4보다 작은 서로 다른 숫자는 (-10, -9, 2) 3개네요. 4는 3을 출력
-10 > Xj → -10보다 작은 서로 다른 숫자는 하나도 없으므로 -10은 0을 출력
-9 > Xj → -9보다 작은 서로 다른 숫자는 (-10) 1개 뿐이고, -9은 1을 출력

결과적으로
[2 : 2, 4 : 3, -10 : 0, -9 : 1]
이렇게 key : value 형태로 저장되는 구조를 딕셔너리 자료구조라고 합니다.
선언은 중괄호로 합니다. dict = { }

딕셔너리안에 key : value 형태로 저장하여 key 값에 따라 value를 출력해주기 하면 되네요.

중복을 제거하기 전 리스트의 숫자에 출력되는 숫자를 해보면
[2, 4, -10, 4, -9] → 2 3 0 3 1
정답 : 2 3 0 3 1

코드를 순서대로 작성한다면
1. 입력된 좌표들을 리스트로 저장
2. 중복 제거를 위해 세트형으로 변환 후 리스트로 변환
3. 딕셔너리 선언
4. 딕셔너리안에 좌표 값과 value 값을 저장
5. 기존 좌표를 딕셔너리안에서 찾아서 value 값을 공백을 두고 출력

 

---

작성 코드

import sys
input = sys.stdin.readline # 입력 시간초과를 방지하기 위해 input을 sys함수로 대체

N = int(input())
arr = list(map(int, input().split())) # 좌표 입력 후 리스트로 저장

set_arr = list(set(arr)) # 중복 제거를 위해 세트형으로 한 후 리스트로 변환

dict_arr = {} # key:value 형태로 저장하기 위한 딕셔너리 선언

for i in range(len(set_arr)): # 중복제거 된 리스트 길이만큼 반복
    dict_arr[set_arr[i]] = i # 좌표 : 0, 좌표 : 1 ... 좌표 : len(set_arr)
    
for i in arr: # 기존 좌표를 하나씩 넣고, 딕셔너리에서 좌표의 value 값을 출력
    print(dict_arr[i], end = ' ') # 공백을 두고 출력