[Python] BOJ/백준 18870번 좌표 압축

[문제]

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

18870번: 좌표 압축

 

[풀이]

좌표 압축이란?

좌표 압축이란 간단하게 데이터를 정렬한 후 순서를 다시 부여하는 것이다. x, y의 범위가 (-10억~10억) 일 경우 20억의 구간에 업데이트를 해야 하는데 이는 불가능하다. 따라서 이를 해결하기 위해서는 문제에 등장하는 좌표는 많지 않기 때문에 등장한 수만을 이용해 좌표를 압축해야 한다. 이를 좌표 압축이라고 부른다.

---

중복되는 숫자를 제거하기 위해 set자료형으로 한번 변환해주는 것이 꼭 필요하다.

따라서 입력받은 수를 list로 저장해 coordinate 리스트에 담고,

해당 리스트를 set으로 변환 -> 다시 리스트로 변환 -> sorted함수로 정렬해 coordinate2 리스트에 담는다.

 

그 후 빈 딕셔너리 dic 를 선언한 후 인덱스에 맞게 값을 넣어준다.

마지막으로 처음 입력받은 순서대로 coordinate 리스트를 이용해 출력한다.

 

[코드]

import sys

if __name__ == '__main__':
    n = int(sys.stdin.readline())
    coordinate = list(map(int, sys.stdin.readline().split()))
    coordinate2 = sorted(list(set(coordinate)))

    dic = {}
    for i in range(len(coordinate2)):
        dic[coordinate2[i]] = i
    for i in coordinate:
        print(dic[i], end=' ')