[백준] 18870번: 좌표 압축

문제

수직선 위에 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

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 = sys.stdin.readline

n = int(input())

시간복잡도를 줄이기 위해 import sys를 하여 input()대신 sys.stdin.readline()을 사용한다. 

매번 sys.stdin.readline을 입력하기 힘드니

input=sys.stdin.readline으로 하여 input()이 sys.stdin.readline()으로 인식하게 한다.

먼저 입력받는 좌표 갯수를 입력받는다. 

 

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

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

arr에 list(map(int,input().split()))으로 숫자들을 리스트에 입력받고

좌표압축을 위해 각 리스트들의 중복을 제거하고 오름차순으로 정렬한다. 

 

dic={}

for i in range(len(arr2)):

    dic[arr[i]]=i

dic이라는 딕셔너리를 하나 생성하고 

입력받은 각 숫자들을 key로 하고, arr2의 인덱스를 값으로 저장한다. 그러면 입력받은 각 숫자에 좌표압축된 번호가 저장된다.

 

for i in arr:

    print(dic[i], end = ' ')

for i in arr:로 하여 arr의 요소들을 순서대로 i에 입력해 dict[i]를 출력한다. 그러면 아까 저장한 dict의 key값(arr2의 인덱스)가 출력된다.

 

정답

import sys

input = sys.stdin.readline

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

arr2 = sorted(list(set(arr)))
dic={}
for i in range(len(arr2)):
    dic[arr[i]]=i
for i in arr:
    print(dic[i], end = ' ')