[백준-Python] 18870번 좌표 압축 파이썬 풀이

단계별로 풀어보기 - [정렬] - 18870번 좌표 압축

문제

---

문제링크

 

풀이

---

x좌표 리스트를 받고, 순서대로 정렬한 다음, 그 순위를 출력해주면 된다.

처음 리스트를 정렬해서 그 인덱스 값을 출력하는 풀이를 생각했다.

 

 

유의할 점은,

✅ 같은 좌표는 같은 순위를 가지므로 압축된 좌표값도 동일하다. 

그냥 정렬된 리스트의 인덱스 값을 출력하면 같은 좌표값도 순위가 다르게 나오기 때문에,

정렬된 좌표들은 set으로 표현하여 중복을 제거해줘야 한다.

 

✅ 시간 복잡도 고려

일단 input()함수보다 sys.stdin.realine 함수가 더 빨라서, 시간 제한이 있는 경우 후자를 선택하는 것이 좋다.

그리고 단순히 처음 입력받은 좌표 리스트의 좌표값을 순서대로 정렬된 리스트에서 찾아서 그 인덱스 값을 출력하도록 하였더니 시간 초과가 떴다.

아무래도 이중 반복문을 썼으니,,ㅎ

 

시간 초과가 났던 풀이

n = int(input())

x_list = [int(x) for x in input().split()]

sorted_list = sorted(set(x_list))

for x in x_list:
    for i in range(len(sorted_list)):
        if x == sorted_list[i]:
            print(i, end=' ')

 

그래서 dictionary 자료형을 이용하여 좌표값을 통해 해당 인덱스 값을 바로 가져올 수 있도록 구현하였다.

{dic[요소]: 요소의 인덱스} 의 형태로 저장함으로써 dic[x]로 값을 뽑을 때 O(1)이 되도록 하였다.

 

참고로 list.index(i)로도 리스트에서 요소의 인덱스 값을 바로 뽑을 수 있는데, 이럴 경우 시간 복잡도는 O(n)이다.

그러나 index[i] 형태는 시간 복잡도가 O(1)로, 더 빠르다. 

 

CODE

import sys
input = sys.stdin.readline

n = int(input())
x_list = [int(x) for x in input().split()]

sorted_list = sorted(set(x_list))

dic = {sorted_list[i]: i for i in range(len(sorted_list))}

for x in x_list:
    print(dic[x], end=' ')

 

결과

---