[백준] 18870번 - 좌표 압축

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

 

✔️ 문제

 

 

문제는 다음과 같다.

 

 

✔️ 풀이

 

 

문제와 예제를 보게 되면, 다음과 같이 이해할 수 있다.

예제 입력 1에서 들어온 숫자를 정렬하게 되면,

-10 -9 2 4 4라는 값을 얻게 되는데,

각각의 값에 해당하는 인덱스를 들어온 입력 자리에

새롭게 출력하는 문제이다.

 

import sys
ss=sys.stdin.readline

N=int(ss())
data=list(map(int,ss().split()))
origin=sorted(list(set(data)))

for i in range(N):print(origin.index(data[i]), end=' ')

 

처음에 다음과 같은 코드를 작성했는데,

중복되는 것은 삭제한 이후에 해당 값이 존재하는

인덱스의 위치를 출력하는 것이었다.

 

하지만, 시간 초과라는 것에 걸리게 되었는데

이유를 생각해보니 X는 -1억~1억까지의 범위를 가지고 있고

for문 O(N)에 index가 O(N)이여서 중첩한

O(N^2)에 대한 시간복잡도를 가지고 있는 것이었다.

 

이 문제를 해결하기 위해서 index를 사용하지 않고도

인덱스를 출력할 수 있는 방법을 생각해보게 되었다.

 

import sys
ss=sys.stdin.readline

N=int(ss())
data=list(map(int,ss().split()))
origin=sorted(list(set(data)))

new={origin[i] : i for i in range(len(origin))}
for i in data:print(new[i], end=' ')

 

중복을 제거하고 정렬된 origin 리스트의 값과 인덱스를

하나의 key와 value로 구성된 딕셔너리로 만들어준다.

 

그리고나서 data에 존재하는 i의 값이 새로운 딕셔너리의

key로 주어졌을 때의 value를 출력하면 정답이 된다.

 

리스트 이외에도 사용 가능한 것이 많다는 것을

잊지않고 딕셔너리도 활용을 자주 해야겠다.

 

 

참고로 동일한 코드를 PyPy3을 통해서 컴파일하면

메모리는 증가하지만 시간을 단축할 수 있는 방법도 있다.

 

화이팅 💪