[18870] 좌표압축

문제

출처
수직선 위에 N개의 좌표 X1, X2, ..., XN이 있다. 이 좌표에 좌표 압축을 적용하려고 한다.
Xi를 좌표 압축한 결과 X'i의 값은 Xi > Xj를 만족하는 서로 다른 좌표 Xj의 개수와 같아야 한다.
X1, X2, ..., XN에 좌표 압축을 적용한 결과 X'1, X'2, ..., X'N를 출력해
보자.

입력
5
2 4 -10 4 -9

출력
2 3 0 3 1

문제 정리

• 왜인지는 모르겠으나 저 몇 줄 안되는 문제를 해석하기가 쉽지 않았다.
• 정리하자면 기존 좌표를 중복제거, 오름차순 정렬하여 해당 인덱스를 반환하라는 의미이다.
• 이분탐색, 집합을 사용하면 문제를 쉽게 풀 수 있다.

문제 풀이

n = int(input()) # 좌표의 개수
num_list = list(map(int,input().split())) # 기존 좌표
# set을 통해 중복제거, 이후 정렬
sorted_num_list = sorted(set(num_list))  

# 이분 탐색
for num in num_list:
    start = 0 # 시작 인덱스
    end = len(sorted_num_list)-1 # 종료 인덱스
    while True: # 원래라면 시작인덱스가 종료 인덱스보다 커진다면 종료(이 문제에서는 기존 리스트를 통해 새로운 리스트를 만든것이기에 탐색이 안되는경우가 없다.)
        mid = (start+end)//2 # mid의 새로운 위치
        if sorted_num_list[mid] == num: # 탐색이 완료되는 조건
            print(mid, end = ' ')
            break
        elif sorted_num_list[mid] < num:
            start = mid+1 # 시작 인덱스를 mid의 다음으로
        else:
            end = mid-1 # 종료 인덱스를 mid의 이전으로

파이썬이기에 아주 쉽게 해결할 수 있지 않았을까? 싶다. set, sort가 이미 잘 구현되어 있기에 말이다. 사실 이분 탐색 또한 구현되어 있지만 for loop로 직접 구현해서 작성했다.

문제 후기

다른 사람들은 어떻게 문제에 접근했나 싶어서 다른 사람들의 코드를 염탐했다. 그 중 직관적인 코드 중 개인적으로 약간 신기한 풀이를 참고해서 풀어봤다.

• 딕셔너리 사용

딕셔너리를 사용하면 리스트보다 더 빠르게 요소에 접근 가능하다는 사실을 새로 알았다. 이는 파이썬에서 딕셔너리를 해쉬테이블로 구현하여 그렇다고 한다.
이처럼 정렬과 그 순위, 탐색이 중요한 문제에서는 딕셔너리를 사용하는 방법도 하나의 좋은 풀이가 될 수 있음을 알았다.

n = int(input())
num_list = list(map(int, input().split()))

sorted_num_list = sorted(set(num_list))  # 중복 제거하고 정렬된 좌표 리스트 생성

coordinate = {}  # 좌표에 대한 순위를 저장하는 딕셔너리

for i, num in enumerate(sorted_num_list):
    coordinate[num] = i  # 좌표에 대한 순위 부여

for num in num_list:
    print(coordinate[num], end=" ")