[백준] 18870 - 좌표 압축

 

문제 출처 : https://www.acmicpc.net/problem/18870

 

문제

수직선 위의 n개의 좌표에 좌표 압축을 적용한다.

Xi를 좌표 압축한 결과의 값은 Xi<Xj를 만족하는 서로 다른 Xj의 좌표의 개수와 같아야 한다.

X1~Xn에 좌표 압축을 적용한 결과를 출력하라.

좌표 압축이란 주어진 숫자의 상대적 크기만 유지하면서 그 숫자들을 0부터 시작하는 연속된 정수로 변환하는 것을 말한다.
참고 자료: https://blog.naver.com/vh00nj0v/223587794515

 

 

입력

• 첫째 줄에 N이 주어짐.
• 둘째 줄에 공백 한 칸으로 구분된 X1,X2~Xn이 주어짐.

 

출력

• 첫째 줄에 좌표 압축을 적용한 결과를 공백 한 칸으로 구분하여 출력한다.

 

문제 풀이 방법

1. N을 변수에 저장한다
2. X1~Xn을 리스트에 입력 순서대로 저장한다.
3. 리스트를 정렬하여 X1~Xn을 딕셔너리의 key로 넣는다.
4. value는 0부터 순차적으로 1씩 증가시켜 넣는다.
5. 입력받은 순서대로 좌표 압축한 값을 리스트에 넣고 출력한다.

 

작성한 코드

import sys

N = int(sys.stdin.readline().strip()) #1
coordinate = list(map(int,sys.stdin.readline().strip().split())) #2

coordinates = {}
num = 0

for coor in sorted(coordinate): #3
    if coor not in coordinates.keys():
        coordinates[coor] = num #4
        num+=1

result = [coordinates[coor] for coor in coordinate] #5

print(' '.join(map(str,result)))
#print(*result)도 가능

 

 

좌표 압축이라는 개념이 잘 이해가 안되었으나 그것만 알면 잘 풀 수 있었던 문제같다.

출력할 때 print(' '.join(map(str,result)))를 print(*result)로 쓸 수도 있는데

코드 길이가 줄고 메모리 사용량도 줄었으나 시간이 더 오래 걸렸다.

알고 넘어가면 될 것 같다.