백준 알고리즘
[백준/Python] 18870_ 좌표 압축
헝그리개발자
2021. 7. 2. 14:32
문제
https://www.acmicpc.net/problem/18870
18870번: 좌표 압축
수직선 위에 N개의 좌표 X1, X2, ..., XN이 있다. 이 좌표에 좌표 압축을 적용하려고 한다. Xi를 좌표 압축한 결과 X'i의 값은 Xi > Xj를 만족하는 서로 다른 좌표의 개수와 같아야 한다. X1, X2, ..., XN에 좌
www.acmicpc.net
코드
import sys
n = int(sys.stdin.readline().rstrip())
numbers = list(map(int, sys.stdin.readline().rstrip().split()))
lst = sorted(list(set(numbers)))
lst_dic = dict()
for i in range(len(lst)):
lst_dic[lst[i]] = i
for num in numbers:
print(str(lst_dic[num]), end=' ')
풀이
입력받은 수들의 중복을 제거하고 오름차순 정렬하여 각각의 순서를 출력하는 문제입니다.
먼저, 중복을 제거하기 위해 집합 자료구조를 사용합니다.
sorted() 함수로 오름차순 정렬합니다.
최종적으로, 해시 자료구조에 (key = 숫자, value = sort된 순서)로 다시 저장하여 빠른 탐색 속도로 답을 출력합니다.