백준 18870번: 좌표 압축 (Python)

문제

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

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

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

입력

첫째 줄에 N이 주어진다.

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

출력

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

 

 

 

---

 

내 풀이

input 값이 저장되어 있는 리스트("num")가 index를 보관할 수 있도록, 각 원소를 [index, nums[index]] 형태로 저장한 후, 첫 번째 원소를 기준으로 정렬. 이후 0부터 시작하여 좌표 압축하였다. 정렬을 2번하기에 아래 풀이에 비해 시간이 2배 이상 걸린다.

 

 

코드

import sys

N = int(sys.stdin.readline())

nums = list(map(int, sys.stdin.readline().split()))
nums = [[i, nums[i]] for i in range(N)]
nums.sort(key=lambda x: x[1])

count = 0
answer = [[nums[0][0], count]]
current_value = nums[0][1]

for i in range(1, N):
    if current_value == nums[i][1]:
        answer.append([nums[i][0], count])
    else:
        current_value = nums[i][1]
        count += 1
        answer.append([nums[i][0], count])

answer.sort(key=lambda x: x[0])

for elt in answer:
    print(elt[1], end = " ")

 

 

풀이

다른 사람들은 훨씬 더 빨리 끝냈기에, 풀이를 봤는데 input값이 있는 list를 정렬하고, dictionary[value] = ['좌표 압축한 value']와 같은 방식으로 dictionary에 값을 저장한다. 이후 input list를 돌면서 dictionary[value]를 출력하면 된다. 코드도 더욱 깔끔하고, 시간도 덜 걸리며 메모리도 덜 차지한다.

 

코드

import sys

dictionary = dict()
N = int(sys.stdin.readline())
nums = list(map(int, sys.stdin.readline().split()))
nums_sorted = sorted(list(set(nums)))
count = 0

for num in nums_sorted:
    if num not in dictionary:
        dictionary[num] = count
        count += 1

for num in nums:
    print(dictionary[num], end = " ")

 

비교