백준 18870번 좌표 압축 [Python]

[Silver II] 좌표 압축 - 18870

문제 링크

성능 요약

메모리: 155280 KB, 시간: 1648 ms

분류

값 / 좌표 압축, 정렬

제출 일자

2024년 4월 1일 13:29:11

문제 설명

수직선 위에 N개의 좌표 X₁, X₂, ..., X_N이 있다. 이 좌표에 좌표 압축을 적용하려고 한다.

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

X₁, X₂, ..., X_N에 좌표 압축을 적용한 결과 X'₁, X'₂, ..., X'_N를 출력해보자.

입력

첫째 줄에 N이 주어진다.

둘째 줄에는 공백 한 칸으로 구분된 X₁, X₂, ..., X_N이 주어진다.

출력

첫째 줄에 X'₁, X'₂, ..., X'_N을 공백 한 칸으로 구분해서 출력한다.

풀이

# 시간초과 난 나의 풀이

import sys
input = sys.stdin.readline

N = int(input())
num = list(map(int, input().split()))
arr = num
arr = list(set(arr))
arr.sort()

for i in num:
    sys.stdout.write("%d "%arr.index(i))

정답률이 그리 높지 않아서 이런 식의 접근으로는 무조건 시간초과가 뜰 거라는 걸 예상했다. for문에서 .index 매서드로 값을 탐색할 때, 시간복잡도가 O(N)이 걸린다고 한다. 즉 N의 범위가 1,000,000까지니까 최대 1,000,000번 반복이 이루어지니 시간초과는 당연한 수순인 것이다. 따라서 시간복잡도를 줄이기 위해서는 dictionery를 사용할 수 있다. dictionery는 시간복잡도가 O(1)이므로 더 빠른 탐색속도를 자랑한다. 아래는 수정한 코드이다.

전체 코드

import sys
input = sys.stdin.readline

N = int(input())
num = list(map(int, input().split()))

''' 입력받은 리스트 원소들의 중복을 없애고, 
    다시 리스트로 지정한 후 정렬'''
arr = sorted(list(set(num)))

''' key에 정렬되어있는 수들이 위치하고
    value에 인덱스(키값보다 작은 값의 개수)
    값이 위치한다.'''
dic = {arr[i] : i for i in range(len(arr))} # ex) { 10: 0, -9: 1, 2: 2, 3: 4 }

for i in num:
    sys.stdout.write("%d "% dic[i])