[백준] 18870 좌표 압축

문제 설명

문제 링크

문제를 처음 확인해보면 설명이 다소 불친절하다고 느껴지지만, 아래의 예제 입출력을 보고 나면 무엇을 해야할지가 꽤 명확해진다.

-10^9^ 부터 10^9^까지 있는 수직선 상에 있는 점들을 가장 작은 수부터 큰 수까지 0부터 N까지 나열하라는 문제다.
여기서, 입력값에 같은 수가 나온다면 해당 수는 새로 나열되어도 같은 출력값을 공유하며, 이것만 해결하면 크게 어려운 문제는 아니다.

문제 풀이

입력받은 값을 리스트에 넣어 set으로 만든 후 해당 값들을 오름차순 정리를 하여
작은 값부터 키값을 0부터 주어 딕셔너리를 활용해 해결하는 방법이 정석적인 방법 같다.

다만 파이썬에는 enumerate라는 함수가 있으며, 해당 함수를 제대로 활용해볼 기회가 없었어서
이를 활용해 문제를 해결해보기로 했다.

N = int(input())

Xn = list(enumerate(map(int, input().split())))

예제를 기준으로, enumerate를 통해 입력받는 값들(2, 4, -10, 4, -9)에 각각 투플 형식으로 번호를 달아준다. 이렇게 되면 리스트 Xn에 들어가는 원소는 [(0,2), (1,4), (2,-10), (3,4), (4,-9)]가 된다.

Xn.sort(key = lambda x : x[1])

final = [-1 for _ in range(N)]
final[Xn[0][0]] = 0

sort함수를 사용해서 Xn 원소들의 두 번째 값을 기준으로 정렬하고,
(Xn의 원소들은 (인덱스, 값)의 투플 형식으로 있기 때문에 x[1]을 기준으로 정렬해야 값의 크기 기준으로 정렬된다)
정렬된 후 리스트 Xn의 원소는 다음과 같은 순서로 되어있다: [(2,-10), (4,-9), (0,2), (1,4), (3,4)]

해당 좌표들에 새로운 좌표(0부터 시작하는 압축된 좌표)를 부여하기 위해 새 리스트를 하나 만들어주고,
이 리스트의 Xn[0][0]번째 원소를 0으로 초기화해준다.
Xn[0][0]은 가장 작은 원소가 입력된 순서이며, 이 때 입력된 값을 새로운 압축 좌표 내에서 0으로 초기 설정하는 작업이다.

이 때 리스트 final의 값은 [-1,-1,0,-1,-1]이다.

curvalue = 1

for i in range(1,len(Xn)):
    if Xn[i][1] != Xn[i-1][1]:
        final[Xn[i][0]] = curvalue
        curvalue += 1
    else:
        final[Xn[i][0]] = final[Xn[i-1][0]]

위의 부분은 Xn의 원소의 갯수만큼 압축 좌표 리스트 final에 값을 채우는 과정이다.
Xn은 이미 실제 입력된 값 기준으로 정렬되어있기 때문에, 같은 수가 반복되어 나온다면 직전과 같은 값을 넣어줄 수 있다.

최종 코드

---

N = int(input())

Xn = list(enumerate(map(int, input().split())))
Xn.sort(key = lambda x : x[1])

final = [-1 for _ in range(N)]
final[Xn[0][0]] = 0

curvalue = 1

for i in range(1,len(Xn)):
    if Xn[i][1] != Xn[i-1][1]:
        final[Xn[i][0]] = curvalue
        curvalue += 1
    else:
        final[Xn[i][0]] = final[Xn[i-1][0]]

print(*final)