[파이썬] 백준 11870번 좌표 압축

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

18870번: 좌표 압축

[문제 이해]

받은 좌표 리스트를 오름차순으로 배열했을 때, 해당하는 리스트의 인덱스를 순서대로 출력하는 문제이다.

좌표 압축이라고 해서 문제 자체를 이해하기 힘들었는데 입력을 보고 위처럼 이해하고 푸니까 더 풀기 쉬웠던 것 같다.

 

[문제 풀이]

1. 입력 받은 리스트를 오름차순으로 정렬하고 리스트의 원소에 해당하는 값을 오름차순 인덱스에 해당하는 값으로 바인딩해주기 위해서 딕셔너리를 만들어서 저장해주는 방식을 사용하려고 했다. 이때 딕셔너리의 사용법이 잘 기억이 안나서 cnt 변수를 따로 사용해주고 이를 1씩 증가시키면서 저장하는데 이때 만약에 같은 숫자가 있다면 cnt를 증가하면 안되도록 처리를 해둔다. 만든 인덱스에 해당하는 key 값만 돌면서 원래 처음에 받았던 좌표 리스트와 key 값을 비교하며 같으면 출력하도록 했으나 시간 초과가 떴다.

import sys
N = int(sys.stdin.readline())
x_list = list(map(int, sys.stdin.readline().split()))

x_sorted_list = sorted(x_list)
x_index = dict()

cnt = 0
for i in range(1, N):
    x_index[x_sorted_list[i-1]] = cnt
    if x_sorted_list[i] != x_sorted_list[i-1]:
        cnt += 1

for i in range(N):
    for j in x_index.keys(): # x_index의 key만 가져와서 비교
        if x_list[i] == j:
            print(x_index[j], end = ' ')

 

2. 그러나 위처럼 어렵게 풀 필요없이 중복을 먼저 제거하여, 정렬을 먼저 하고 새로운 리스트에 저장한다. 딕셔너리를 생성하여 새로운 리스트를 정렬된 순서대로 인덱스 값을 부여하여 딕셔너리에 저장한다. 이후 입력 받았던 x 리스트의 원소 순서대로 돌면서 딕셔너리의 키 값에 x 리스트의 원소가 들어가면서 딕셔너리의 키에 해당하는 값을 출력한다.

import sys
N = int(sys.stdin.readline()) # 좌표개수
x = list(map(int, sys.stdin.readline().split())) # 좌표값

x_list = sorted(list(set(x))) # 중복 제거 후, 정렬하고 새로운 리스트에 저장

x_dict = dict() # 딕셔너리 생성
for i in range(len(x_list)): # x_list를 돌면서
    x_dict[x_list[i]] = i # x_list에 정렬된 순서대로 인덱스 값을 부여하여 딕셔너리에 저장 
    # {-10:0, -9:1, 2:2, 4:3}
for i in x: # 입력받았던 x 리스트의 원소 순서대로 돌면서
    print(x_dict[i], end= ' ') # 딕셔너리의 키 값에 x 리스트의 원소가 들어가면서 딕셔너리의 키에 해당하는 값이 결과로 나옴