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

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

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

18870번: 좌표 압축

실버 2

정렬

---

접근

입력받은 값을 오름차순 정렬하여 또 다른 리스트에 값을 저장한다면 다음과 같이 될 것이다.

 

nums = [2, 4, -10, 4, -9]

new_nums = [-10, -9, 2, 4, 4]

 

new_nums에서 가장 작은 값을 기준으로 0부터 값을 부여하면

new_nums = [0, 1, 2, 3, 3]가 된다.

 

결국 nums내의 값을 크기가 작은 순서대로 인덱스 값으로 출력하는 것과 같으므로

2 3 0 3 1을 출력하도록 해야한다.

 

import sys; input = sys.stdin.readline
n = int(input())
nums = list(map(int, input().split()))

new_nums = sorted(list(set(nums)))

for i in nums:
    print(new_nums.index(i), end=' ')

 

중복된 값을 제거하고 정렬된 리스트를 new_nums에 할당했다.

그리고 입력받은 값을 저장한 nums의 순서대로 new_nums의 인덱스 값을 차례대로 출력하는 방법을 사용했다.

 

그러나 문제의 조건에 따르면 입력받는 값의 범위가 1,000,000까지이기 때문에 시간 복잡도가 O(N)인 index함수를 사용하면 시간 초과가 난다는 점을 간과했다.

 

따라서 딕셔너리에 정렬된 값과 그 값의 인덱스를 key와 value값으로 할당하여 nums의 순서대로 value값을 뽑아내는 방법을 사용했다. 딕셔너리의 요소를 뽑아내는 방법은 시간복잡도가 O(1)이기 때문에 시간초과가 나지 않았다.

 

코드

import sys; input = sys.stdin.readline
n = int(input())
nums = list(map(int, input().split()))

new_nums = sorted(list(set(nums)))
dic = {new_nums[i] : i for i in range(len(new_nums))}
for i in nums:
    print(dic[i], end=' ')

 

딕셔너리의 키값은 입력받은 값을 오름차순 정렬시킨 new_nums를 대상으로 하므로 다음과 같은 값이 할당된다.

 

dic = {-10: 0, -9: 1, 2: 2, 4: 3}

key값에는 입력한 값이, value값에는 인덱스 값이 할당된다.

이것을 입력받은 순서대로 키값에 접근해 value값을 출력하도록 하면 답을 얻어낼 수 있다.