[BOJ/Python] 18870_좌표 압축

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

[18870번: 좌표 압축

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

www.acmicpc.net](https://www.acmicpc.net/problem/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^9 ≤ Xi ≤ 10^9

예제 입력 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

---

풀이

우선 예제 입력과 출력을 살펴보자.

5

2 4 -10 4 -9

의 경우, 5개의 좌표 [2,4,-10,4,-9]를 입력받게 된다. 문제에서 Xi에 좌표 압축을 적용하게 되면 Xi>Xj를 만족하는 서로 다른 좌표의 개수가 된다고 하였으니, 2를 살펴보면 2보다 작은 서로 다른 좌표는 -10, -9 두개이므로, 좌표 압축을 적용하게 되면 2가 된다. 마찬가지로 4의 경우, 4보다 작은 서로 다른 좌표는 2, -10, -9 세개이므로, 좌표 압축을 적용하게 되면 3이 된다. 최종적으로 좌표 압축 후 결과는 [2,3,0,3,1]가 된다.

자신보다 작은 서로 다른 좌표의 개수를 세는 문제임을 알 수 있다. 이를 바탕으로 코드를 작성하면 다음과 같이 문제를 풀 수 있다.

 

import sys
import bisect
 
n = int(sys.stdin.readline())
n_list = list(map(int,sys.stdin.readline().split()))
sorted_list = sorted(set(n_list))
 
for i in n_list:
    print(bisect.bisect_left(sorted_list,i),end=' ')

1. binary search를 사용하기 위해 bisect 모듈을 import한다.
2. 좌표의 개수 n을 입력받고, n_list에 좌표를 list 형태로 저장한다.
3. 자신보다 작은 서로 다른 좌표의 개수의 개수를 세야 하기때문에, 중복을 제거하기 위해 set()을 이용하고, binary search를 사용하기 위해 오름차순으로 정렬한 리스트인 sorted_list를 만든다.
4. for문을 이용하여 n_list의 좌표를 하나하나 살펴보며, 자신보다 작은 좌표의 개수를 출력한다.

• bisect.bisect_left(sorted_list,i)란, sorted_list에 i를 몇번째 index에 삽입할 수 있는지 확인하는 함수이다.
• 예를들어, sorted_list = [1,3,5,7,9]이고, i = 3이라면, 3의 경우, index 1 또는 2에 삽입될 수 있는데, bisect_left의 경우 제일 왼쪽값을 return하게 되고(여기서는 1을 return), bisect_right를 이용할 경우 제일 오른쪽값을 return한다. (여기서는 2를 return한다.)
• 이 문제에서 bisect_left()를 이용하여 본인보다 작은 좌표의 개수를 구하였다.

이 문제에서는 필요없지만, 추가적으로 알아둘만한 내용이다.

• bisect.bisect_left()와 bisect.bisect_right()를 이용하면, 해당 원소가 리스트에 몇개 존재하는 지 구할 수 있다.
• 두 값의 차이가 곧 원소의 개수가 된다.

 

딕셔너리 자료형을 이용하여 문제를 풀 수도 있다.

import sys
 
n = int(sys.stdin.readline())
n_list = list(map(int,sys.stdin.readline().split()))
sorted_list = sorted(set(n_list))
dict = {}
 
for i,num in enumerate(sorted_list):
    dict[num]=i
 
for num in n_list:
    print(dict[num],end=' ')

 

1. 중복을 제거하고 오름차순으로 정렬된 리스트 sorted_list를 만든다.
2. index와 값을 enumerate를 이용하여 받아오고, 딕셔너리 자료형에 key는 그 수, value는 index로 하여 딕셔너리 쌍을 저장한다. (오름차순이기 때문에 제일 작은 수가 index 0 이고, 이는 곧 이 수보다 작은 수가 0개라고 생각할 수 있다.)
3. for문을 이용하여 리스트의 변수를 key로 하여 value를 출력한다.