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

문제

포인트

정답을 보는것은 어렵지 않다. 하지만, 시간 초과 많이 나는 문제인 것 같다.
그래서 시간을 어떻게 줄이는가? 가 중요한 문제 같다.

풀이

import sys, heapq
input = sys.stdin.readline
sys.setrecursionlimit(10**6)

n = int(input())
X = list(map(int, input().split()))

x_c = sorted(set(X))

X_dict = {}
for i in range(len(x_c)):
    X_dict[heapq.heappop(x_c)] = i

for j in X:
    print(X_dict[j], end = " ")

해설

문제 보자마자 생각했던 것은 set, heapq, dictionary라서 이것들을 가지고 풀이를 해보았다.

x_c에 중복을 제거한 X를 정렬해 놓고, 딕셔너리로 순서에 따라 인덱스를 붙여줘서 각 값에 같게 프린트 했다.

오류

아래 코드 올리겠지만, 시간 초과를 봤는데 나같은 경우는 정렬에 문제였다.
시간복잡도가 헷갈려서 sorted하면 초과 나겠지? 해서 여러방법을 썼는데, sorted가 제일 빨랐다.

또 heapq이 아직 익숫하지 않아서
x= heapq.heaify(X) 를 했는데 print해보면 none이라고 나왔다.
찾아보니 heapq을 메서드라서 원본을 바꿔 heapq.heaify(X)이렇게 사용해야했다.

오류 코드

import sys, heapq
input = sys.stdin.readline
sys.setrecursionlimit(10**6)

n = int(input())
X = list(map(int, input().split()))

# sorted 대신 heappush를 사용했었다
x_c = []
for x in X:
    if x not in x_c:
        heapq.heappush(x_c, x)

X_dict = {}
for i in range(len(x_c)):
    X_dict[heapq.heappop(x_c)] = i

for j in X:
    print(X_dict[j], end = " ")

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**6)

n = int(input())
X = list(map(int, input().split()))
X_set = list(set(X))


X_dict = {}
import heapq

# 정렬를 위해 heapift → heappop을 사용하였다
for i in range(len(X_set)):
    heapq.heapify(X_set)
    X_dict[heapq.heappop(X_set)] = i

for j in X:
    print(X_dict[j], end = " ")