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

■ 18870번 좌표 압축 문제

 

출처: 백준 18870번 좌표 압축 문제

 

■ 코드 풀이

 

여러분, 좌표 압축에 대한 개념을 알고 있으신가요? 저는 이 개념을 몰라서 문제를 한참 읽었습니다. 역시 알고리즘이란 배워도 배워도 끝이 없네요. 좌표 압축이란 좌표를 정렬하고 이를 순서로 표현한 것입니다. 예를 들어 볼까요?

먼저 1, 50, 1000, 50,000, 10,000,000의 5가지 숫자가 있다고 가정하겠습니다. 이 숫자를 그냥 심플하게 1, 2, 3, 4, 5로 표현한 것이 좌표 압축입니다. 이런 맵핑은 특히 입력받는 숫자의 범위가 아주 큰 경우에 유용합니다. 예를 들어 입력값이 -10억부터 10억까지이고 이 사이에서 어떤 연산을 해야 할 경우, 20억 개의 숫자를 모두 업데이트하는 것은 비효율적입니다. 그저 입력받은 숫자들을 정렬하고 순위로 다시 네이밍 하면 훨씬 효율적입니다. (이와 관련된 상세 내용은 코드 아래에 링크로 넣어두었습니다.)

 

돌아와서 결국 이 문제의 핵심은 좌표를 정렬하고 정렬된 좌표에 순서를 맵핑하는 것임을 알게 되었습니다. 순서를 부여할 때 중복되는 숫자는 어차피 같은 순서이기 때문에 제거해줘야 합니다. 그래서 입력 값을 모아둔 list에 set을 취하고 다시 list로 변환한 다음, 이 'unique list'를 정렬해 줍니다.

그리고 정렬된 리스트의 길이와 동일한 길이의 index 길이를 만들어줍니다. 이 두 개의 리스트를 dictionary로 묶어주면 입력받은 숫자가 key값이 되고 그 숫자의 순서가 value가 되는 dict 자료형이 만들어집니다. 나머지는 입력받은 값의 원본 list에서 숫자를 하나씩 꺼내서 dict에 매칭하면 됩니다.

제가 이 문제를 풀면서 또 헷갈렸던 개념은 두 개의 리스트로 dict를 만드는 것이었는데요, 해당 개념도 코드 아래에 링크로 넣어두었으니 참고해 주세요. 

 

N = int(input())

num_list = list(map(int, input().split()))
unique_num_list = list(set(num_list))
unique_num_list.sort()

idx_list = [i for i in range(len(unique_num_list))]

num_idx_dict = {key : value for key, value in zip(unique_num_list, idx_list)}


for num in num_list:
    print(num_idx_dict[num], end = ' ')

 

 

 

[참고] 좌표 압축

https://jason9319.tistory.com/356

좌표압축 기법

 

 

[참고] 2개의 리스트로 파이썬 dictionary 자료형 만들기

https://hengbokhan.tistory.com/130

[Python] 리스트 두 개로 dict 만들기