[BOJ] 18870. 좌표 압축(python)

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

18870번: 좌표 압축

 

문제 설명

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

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

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

 

첫째 줄에 N이 주어진다.

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

 

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

 

문제 해결

import sys
input = sys.stdin.readline

N = int(input())
arr = list(map(int,input().split()))
answer = []
dic = {}
tmp = sorted(set(arr))
com = {}
for i in range(len(tmp)):
    com[tmp[i]] = i
for i in range(len(arr)):
    dic[arr[i]] = com[arr[i]]
for i in range(len(arr)):
    print(dic[arr[i]], end=' ')

 

문제 풀이 설명

먼저 이 문제는 시간복잡도가 중요한 문제이다. 이 문제를 통해 python 함수들의 각 시간 복잡도를 학습하고 최대한 시간복잡도를 줄일 수 있는 방법에 대해 고민해 볼 수 있었던 아주 좋은 문제였다.

고민의 흔적

먼저 처음에는 이중 for문으로 시간복잡도가 O(n^2)가 나와 실패했다.

이때는 단순히 입력받은 arr 리스트를 두번 반복하며 만약 arr[i]가 arr[j]보다 크다면 그 개수를 더해 저장한 후 출력했다.

(당연히 시간초과 뜨지..) 그래서 dictionary를 이용해야겠다고 생각했다.

세 번째 풀이에서는 for문을 한개로 줄이고 중복을 없애기 위해 set()을 이용해 tmp 리스트를 하나 만들었다.

dictionary를 이용해 key로 arr의 각 값을, value로 tmp에서 arr의 각 값을 기준으로 index() 함수를 사용해 슬라이싱을 이용했다.

dic[arr[i]] = len(tmp[:tmp.index(arr[i])])

하지만 슬라이싱은 a에서 b까지일때 O(b-a)의 시간복잡도가 걸린다는 것을 알았다. 결국 O(n^2)으로 수렴할 수 있기 때문에 폐기했다.

일곱 번째 풀이에서 드디어 문제를 해결했는데(1시간 반정도 고민했던 것 같다.)

내가 계속 초점을 맞추고 있던 곳은 출력의 숫자였다. 결국 자신보다 작은 값의 개수를 알면(중복을 제거하고) 된다는 시선이였는데 계속 들여다 본 결과(tmp를 정렬한 출력값을 보며) 결국 index 처럼 0부터 증가한다는 것을 깨달았다.

예제에서 데이터 값의 범위인 -10^9 조차도 결국 가장 작은 값이라면 결과값은 0이다. 그것보다 큰 수가 하나씩 나올때마다 +1씩 해주면 된다는 것을 깨닫고 index()와 슬라이싱을 이용하지 않고도 해결할 수 있겠다고 생각했다.

 

그래서 com(pare)이라는 dictionary를 하나 생성해 입력받은 리스트 별로 i를 하나씩 증가시키며 인덱스를 저장했으며,

arr의 길이를 돌며 각 인덱스의 값을 저장했다.(기존에 슬라이싱, index()함수를 통해 값을 저장한 부분)

그 후 출력해주면 문제는 해결된다.

 

정렬 파트는 해결하고 다음 알고리즘으로 넘어갈 수 있어 너무 행복하다.