[알고리즘] 수직선 위의 좌표압축(백준 18870번 좌표압축 파이썬)

좌표 압축 개념 설명

좌표 압축은 주어진 좌표들을 상대적인 순서를 유지하면서 더 작은 범위의 값으로 변환하는 기법입니다. 이 기술은 주로 알고리즘의 효율성을 높이기 위해 사용됩니다. 특히 큰 수를 다루거나 좌표 간의 상대적인 순서만 필요한 경우 매우 유용합니다.

왜 좌표 압축을 사용하는가?

좌표 압축을 사용하면 다음과 같은 장점이 있습니다:

1. 메모리 절약: 좌표의 값 범위를 줄임으로써 메모리 사용을 줄일 수 있습니다.
2. 알고리즘 효율성: 좌표의 값이 작아지면, 특정 알고리즘(예: 정렬, 탐색, 세그먼트 트리, 펜윅 트리 등)의 성능이 향상될 수 있습니다.
3. 단순화: 문제를 단순화하여 더 쉽게 해결할 수 있습니다.

좌표 압축의 원리

좌표 압축의 기본 아이디어는 각 좌표를 그 좌표의 순위(rank)로 변환하는 것입니다. 순위는 해당 좌표보다 작은 서로 다른 좌표의 개수로 정의됩니다. 이를 통해 좌표의 상대적인 순서를 유지할 수 있습니다.

좌표 압축 과정

1. 중복 제거 및 정렬: 주어진 좌표 리스트에서 중복을 제거하고, 남은 좌표를 오름차순으로 정렬합니다.
2. 압축된 값 매핑: 정렬된 좌표 리스트에서 각 좌표의 순위를 매핑합니다. 이때, 작은 좌표부터 시작하여 0, 1, 2, ... 와 같이 순위를 부여합니다.
3. 좌표 변환: 원래 좌표 리스트를 순회하면서 각 좌표를 압축된 값(순위)으로 변환합니다.

 

 

예시로 백준 문제를 가져왔습니다. 파이썬으로 풀이해보겠습니다.

 

백준 18870번 좌표압축 문제

 

 

예제:

입력

5
2 4 -10 4 -9

 

출력:

2 3 0 3 1

풀이 방법

1. 입력 받기: 표준 입력으로부터 좌표의 개수 N과 좌표 리스트를 입력 받습니다.
2. 중복 제거 및 정렬: 좌표 리스트에서 중복을 제거하고 정렬합니다.
3. 압축된 값 매핑: 정렬된 리스트를 이용해 각 좌표를 압축된 값으로 매핑합니다.
4. 좌표 압축 적용: 원래 좌표 리스트를 압축된 값으로 변환합니다.
5. 결과 출력: 변환된 좌표 리스트를 출력합니다.

 

 

 

import sys
input = sys.stdin.readline

# 입력 받기
N = int(input().strip())
coords = list(map(int, input().strip().split()))

# 중복 제거 및 정렬
sorted_unique_coords = sorted(set(coords))

# 압축된 값 매핑
coord_to_compressed = {value: idx for idx, value in enumerate(sorted_unique_coords)}

# 원래 좌표 리스트를 압축된 값으로 변환
compressed_coords = [coord_to_compressed[value] for value in coords]

# 결과 출력
print(' '.join(map(str, compressed_coords)))

 

 

압축된 값 매핑부터 이게 뭐하는거지? 하시는 분들도 있을거라고 예상합니다. 처음 보는 유형이라면 충분히 그럴만해요

 

coord_to_compressed = {value: idx for idx, value in enumerate(sorted_unique_coords)}

이 코드를 상세하게 살펴보겠습니다.

 

이 코드는 정렬된 유니크 좌표 리스트 sorted_unique_coords를 사용하여 각 좌표에 대해 압축된 값을 매핑하는 사전을 생성합니다.

1. sorted_unique_coords 리스트: 중복을 제거하고 정렬된 좌표 리스트입니다.

sorted_unique_coords = sorted(set(coords))

   2. enumerate 함수: 이 함수는 리스트를 인덱스와 값의 쌍으로 반환합니다.

enumerate(sorted_unique_coords)

이는 [(-10, 0), (-9, 1), (2, 2), (4, 3)]와 같이 각 좌표와 그에 해당하는 인덱스(순위)를 반환합니다

 

   3. 사전 생성: 딕셔너리 컴프리헨션을 사용하여 각 좌표에 대해 압축된 값을 매핑하는 사전을 만듭니다.

{value: idx for idx, value in enumerate(sorted_unique_coords)}

이는 다음과 같은 사전을 생성합니다.

{-10: 0, -9: 1, 2: 2, 4: 3}

즉, coord_to_compressed 사전은 각 좌표를 그 좌표의 압축된 값(순위)으로 매핑합니다.

 

원래 좌표 리스트를 압축된 값으로 변환

코드

compressed_coords = [coord_to_compressed[value] for value in coords]

설명

이 코드는 원래 좌표 리스트 coords를 압축된 값으로 변환한 리스트를 생성합니다.

1. 리스트 컴프리헨션: 리스트 컴프리헨션을 사용하여 원래 좌표 리스트를 순회하며 각 좌표를 압축된 값으로 변환합니다.이는 coords 리스트의 각 값을 coord_to_compressed 사전을 이용해 압축된 값으로 변환하여 새로운 리스트를 만듭니다.
    

   [coord_to_compressed[value] for value in coords]

2. 예시:원래 좌표 리스트의 각 값을 coord_to_compressed 사전에서 찾아 변환하면:

coords = [2, 4, -10, 4, -9]
coord_to_compressed = {-10: 0, -9: 1, 2: 2, 4: 3}

즉, compressed_coords 리스트는 원래 좌표 리스트의 각 좌표를 압축된 값으로 변환한 결과입니다.