[백준] 정렬 - 18870번 (Python)

https://www.acmicpc.net/problem/18870

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 ≤ N ≤ 1,000,000
• -10⁹ ≤ Xi ≤ 10⁹

코드 정답

import sys
input = sys.stdin.readline

n = int(input())
li = list(map(int, input().split()))
li_2 = sorted(list(set(li)))

dic = {li_2[i] : i for i in range(len(li_2))}

for i in li:
    print(dic[i], end = ' ')

풀이

1~2행 : 일반적으로 input 을 사용하게 된다면 시간 초과가 나올 수 있다. 그렇기 때문에 input 과 같으면서도 빠른 sys.stdin.readline 을 사용하기 위해 import sys 란 헤더를 선언해주었고 input 에 sys.stdin.readline 을 대입하여 input 을 sys.stdin.readline 처럼 사용 할 수 있게끔 된다.

import sys
input = sys.stdin.readline

4~6행 : 값을 입력받고 변수 n 에 대입한다. 다음 줄에는 값을 공백 단위로 입력을 받아주고 그것을 list  형태로 변수 li 에 저장한다. 이후 li 에 저장된 값을 set(집합) 형식으로 바꿔 중복값을 없애주고 다시 list 형식으로 바꾼 후 sorted 를 이용하여 li 를 정렬한 값을 li_2 에 대입시킨다.

n = int(input())
li = list(map(int, input().split()))
li_2 = sorted(list(set(li)))

8행 : dict(딕셔너리) 형식으로 바꾼 것이다. 순서대로 설명을 해보자면

li_2에 저장되어 있는 값의 갯수에 따라 길이를 구하게 된다. 길이를 구했으면 그 길이의 값 만큼 반복이 되는데, li_2의 처음에 저장된 값을 0, 그 다음 값은 1, 이런 식으로 정렬된 값의 값을 0부터 순차적으로 붙여주며 dic의 인덱스에 저장하게 된다.

dic = {li_2[i] : i for i in range(len(li_2))}

10~11행 : i 가 li 의 값을 따라가며 dic[i] 에 저장된  값을 출력하게 된다. 다만 한 줄씩 출력이 되는게 아닌, end = ' ' 를 이용하여 공백마다 출력할 수 있게끔 해주었다.

for i in li:
    print(dic[i], end = ' ')