99클럽 코테 스터디 파이썬 비기너 22일차 좌표 압축

🤔 문제

문제
수직선 위에 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 ≤ N ≤ 1,000,000
-109 ≤ Xi ≤ 109

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

 

알고리즘 분류
정렬, 값 / 좌표 압축

From Baekjoon, https://www.acmicpc.net/problem/18870

✨ 답안

import sys

# 1. Get data
cnt = int(sys.stdin.readline().strip())
points = list(map(int, sys.stdin.readline().strip().split()))

# 2. Sort elements after removing duplicated elements
sorted_points = sorted(set(points))

# 3. Count the number of smaller values than itself
compressed_points = {}
for i in range(len(sorted_points)):
    compressed_points[sorted_points[i]] = i

# 4. Map elements and print the result
answer = []
for point in points:
    answer.append(compressed_points[point])

sys.stdout.write(' '.join(str(ans) for ans in answer))

## v3

✨ 원리

1. 입력을 받는다.
2. 중복을 제거하기 위해 입력받은 좌표의 리스트를 집합으로 만들고, 오름차순으로 정렬한다.
3. 딕셔너리에 값의 압축 결과를 저장한다. 이때, 키와 값은 각각 원래 좌표의 값, 압축된 좌표의 값으로, 압축된 좌표는 중복이 제거되고 오름차순으로 정렬된 배열에서 자신의 인덱스와 같다.
4. 처음 입력받은 좌표의 리스트를 기준으로 반복한다. 딕셔너리에서 자신(키)이 가지는 밸류가 자신의 압축 결과와 같으므로, 결과 배열에 이를 하나씩 저장한다.
5. 결과를 출력한다.

💻 구현

points = list(map(int, sys.stdin.readline().strip().split()))

• map()의 반환값은 map 객체이기 때문에 리스트로 변환해주면 우리 입맛에 맞게 (정상적으로) 쓸 수 있다.

 

😥 오류

• 중복을 다루는 데 신중해야 한다. 정렬 이전에 요소를 집합으로 만들어 중복 요소를 제거하지 않으면, 중복 값까지 세어 자신의 위치를 파악하기 때문에 원하는 값보다 더 큰 값이 출력되는 문제가 발생한다. 정렬 시에는 중복을 제거해도 되는 이유가, 마지막 결과 출력 시에는 원래 배열을 기준으로 매핑해서 출력하기 때문이다. 중복은 알아서 원래 배열의 값이 알아서 딕셔너리에서 자신의 값을 찾아 출력한다.

😂 후기

탐색이 필요하다면 얼른 딕셔너리를 꺼내오자.