[백준] 18870번 좌표 압축 - 파이썬

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

18870번: 좌표 압축

풀이

목표: 공백을 포함한 숫자들이 주어진다. 주어진 숫자들을 하나씩 다른 수들과 비교하여 보다 작은 수의 개수를 출력하는 문제입니다. 다만 중복된 숫자는 계산을 한번만 합니다.

예제)

주어진 숫자들: [1, 3, 5]

1은 다른 숫자인 3, 5보다 작은 숫자이다. 고로 1보다 작은 숫자의 개수는 0개이다.

3은 다른 숫자인 1보다 크고, 5보다 작다. 고로 3보다 작은 숫자의 개수는 1개이다.

5는 다른 숫자인 1, 3보다 크다. 고로 5보다 작은 숫자의 개수는 2개이다.

정답: [0, 1, 2]

 

시간초과로 인해 문제의 해설을 찾아보려온 사람들이 많을 것이다.

이 문제를 풀기위해서는 시간소모를 줄이기 위해 dictionary와 인덱스를 이용해줄것입니다.

 

이 문제에서 작은 숫자의 개수를 찾는 것은 숫자들을 오름차순으로 정렬했을 때 인덱스와 같습니다.

이것을 이용해서 딕셔너리와 함께 사용해줍시다.

# 18870 좌표 압축
n = int(input())
nums = list(map(int, input().split()))
# 중복되는 수를 제거해줍니다.
remove_overlap = list(set(nums))
# 오름차순으로 수를 정렬해줍니다.
remove_overlap.sort()
length = len(remove_overlap)
ans_dic = {remove_overlap[i]: i for i in range(length)}

for i in nums:
    print(ans_dic[i], end = " ")

출력결과