백준 18870 : 좌표 압축 (Python)

본문 링크

import sys
input=sys.stdin.readline
import copy

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

L2=copy.deepcopy(L)

L2=set(L2)
L2=list(L2)
L2.sort()

dict={}
for i in range(len(L2)):
    dict[L2[i]]=i

for i in range(N):
    print(dict[L[i]] , end=" ") 

📌 어떻게 접근할 것인가?

문제는 간단하다. 리스트 값이 주어질때 그 값보다 작은 값들의 개수를 구하면 된다.

예제입력을 보자.

• 5
  2 4 -10 4 -9

이때 2보다 작은 값은 -10 , -9 이므로 개수는 2가된다.
4보다 작은 값은 2,-10,-0 이므로 개수는 3이된다.
-10보다 작은값은 없으므로 개수는 0 이 된다.
-9보다 작은값은 -10 이므로 개수는 1이된다.

따라서 예제출력의 답은

• 2 3 0 3 1

위와 같다.

문제는 간단하지만 수의 범위를 보자. $N$ 과 $X_i$ 의 범위가 $1 ≤ N ≤ 1,000,000$ , $-10^9 ≤ X_i ≤ 10^9$ 이다.

즉 완전탐색을 통한 $O(N^2)$ 풀이는 불가능하다.

총 3번째 접근을 하였다.

📌 첫번째 접근

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

L2=copy.deepcopy(L)

L2=set(L2)
L2=list(L2)
L2.sort()

for i in range(N):
    print(L2.index(L[i]) , end=" ")

$L2$ 라는 새로운 배열을 만들어서 정렬하고 $L2.index(L[i])$ 를 출력한다.
하지만 index 는 시간복잡도가 최대 $O(N)$ 이므로 시간초과가 발생하였다.

📌 두번째 접근

import sys
input=sys.stdin.readline
import copy

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

L2=copy.deepcopy(L)

L2=set(L2)
L2=list(L2)
L2.sort()

dp=[0]*(abs(min(L))+abs(max(L)))

for i in range(len(L2)):
    dp[L2[i]]=i

for i in range(N):
    print(dp[L[i]] , end=" ")

$dp$ 배열을 선언해서 $O(1)$ 의 시간복잡도로 매번 원할때마다 바로 값을 출력하게 만들었다.
하지만 $X_i$ 범위가 너무 크기 때문에 메모리 초과가 발생하였다.

📌 마지막 접근

따라서 본문에 가장 위에있는 코드로 제출해서 AC 를 받았다.
바로 딕셔너리 를 사용한 것이다. 딕셔너리를 통해 리스트을 정렬해서
키-값을 통해서 리스트 값이 정렬후 몇번째 순서인지 저장을 해준다.

이후 원소를 꺼낼때도 딕셔너리는 $O(1)$ 의 시간복잡도로 찾을 수 있으므로 제한시간안에 문제를 풀 수 있다.