[백준] 18870 : 좌표 압축 (Python/파이썬)

문제 링크

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

문제

수직선 위에 N개의 좌표 X1, X2, ..., XN이 있다. 이 좌표에 좌표 압축을 적용하려고 한다.

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

X1, X2, ..., XN에 좌표 압축을 적용한 결과 X'1, X'2, ..., X'N를 출력해보자.

- 제한
1 ≤ N ≤ 1,000,000
-109 ≤ Xi ≤ 109

입력

첫째 줄에 N이 주어진다.

둘째 줄에는 공백 한 칸으로 구분된 X1, X2, ..., XN이 주어진다.

출력

첫째 줄에 X'1, X'2, ..., X'N을 공백 한 칸으로 구분해서 출력한다.

예제

입력

5
2 4 -10 4 -9

출력

2 3 0 3 1

---

정답 및 풀이

내가 푼 풀이

import sys

n = int(sys.stdin.readline())
arr=list(map(int,sys.stdin.readline().split()))
result=[0]*n
for i in range(n):
    for j in range(n):
        if arr[i] > arr[j]:
            result[i] += 1

print(*result)

• 시간복잡도가 O(n²) 이 나오면서 시간 초과로 실패

정답 풀이

import sys

n = int(sys.stdin.readline())
arr = list(map(int, sys.stdin.readline().split()))

sorted_arr = sorted(set(arr))
rank = {v: i for i, v in enumerate(sorted_arr)}

result = [rank[x] for x in arr]
print(*result)

1. sorted_arr = sorted(set(arr))
   • set()으로 중복 제거, sorted()로 오름차순 정렬한다.
   • 예: arr = [3, 8, 2, 5, 8] → sorted_arr = [2, 3, 5, 8]
2. rank = {v: i for i, v in enumerate(sorted_arr)}
   • 각 숫자에 몇 번째로 작은 수인지 를 저장한다.
   • 예: {2:0, 3:1, 5:2, 8:3}
   • 값 → 인덱스 매핑 (O(1) 접근 가능)
3. result = [rank[x] for x in arr]
   • 원래 입력 순서대로 순위를 가져온다.
   • 예: [3, 8, 2, 5] → [1, 3, 0, 2]
4. print(*result)
   • 리스트를 공백으로 구분하여 한 줄에 출력한다.

---

새롭게 배운 내용 및 느낀점

• 딕셔너리

메서드 / 표현 설명 예시 출력 결과

dict[key]	key로 value 조회 (없으면 에러)	rank[3]	1
dict.get(key)	key로 value 조회 (없으면 None 반환)	rank.get(10)	None
dict.get(key, 기본값)	key가 없을 때 기본값 반환	rank.get(10, -1)	-1
dict.keys()	모든 key를 반환 (반복 가능)	rank.keys()	dict_keys([2, 3, 5, 8])
dict.values()	모든 value를 반환	rank.values()	dict_values([0, 1, 2, 3])
dict.items()	(key, value) 쌍을 반환	rank.items()	dict_items([(2, 0), (3, 1), (5, 2), (8, 3)])
key in dict	key 존재 여부 확인 (True/False)	3 in rank	True
dict.pop(key)	key에 해당하는 항목 제거 후 value 반환	rank.pop(3)	1
dict.update({key:value})	기존 딕셔너리에 항목 추가 또는 수정	rank.update({9:4})	{2:0, 3:1, 5:2, 8:3, 9:4}
len(dict)	항목 개수 반환	len(rank)	4