[백준 코딩테스트(Python)] 정렬 - 좌표 압축

18870번: 좌표 압축

---

문제

수직선 위에 N개의 좌표 X1, X2, ..., XN이 있다. 이 좌표에 좌표 압축을 적용하려고 한다.

Xi를 좌표 압축한 결과 X'i의 값은 Xi > Xj를 만족하는 서로 다른 좌표의 개수와 같아야 한다.

X1, X2, ..., XN에 좌표 압축을 적용한 결과 X'1, X'2, ..., X'N를 출력해보자.

 

입력

첫째 줄에 N이 주어진다.

둘째 줄에는 공백 한 칸으로 구분된 X1, X2, ..., XN이 주어진다.

 

출력

첫째 줄에 X'1, X'2, ..., X'N을 공백 한 칸으로 구분해서 출력한다.

 

제한

• 1 ≤ N ≤ 1,000,000
• -109 ≤ Xi ≤ 109

 

---

1. 문제 접근 방식

1) 좌표 압축이란?

'좌표 압축'은 여러 좌표들을 연속된 수들로 모아 압축하는 것을 말한다.

[1, 10, 100, 1000] 4개의 좌표가 있다면, 좌표는 4개지만 좌표 값은 1부터 1000까지 있는 것이다.

이 4개의 좌표를 압축하면 [0, 1, 2, 3]이 된다.

 

결국, 작은 값부터 순서대로 정렬한 값의 인덱스가 되는 것이다.

 

이 부분이 이해되지 않아 구글링을 해보았다. (아래 참고 블로그 확인하면 더 자세히 설명되어있음!)

 

2) 코드 진행 순서

① 중복이 된 상태에서 인덱스를 부여해주면 안되기에 set()으로 중복을 제거해준 후 정렬을 한다.

② 딕셔너리를 활용하여 value 값에 인덱스를 부여해준다.

③ 부여된 인덱스 딕셔너리와 중복 제거 및 정렬한 입력값을 활용하여 value 값을 출력해준다.

 

 

2. 풀이 코드

# 딕셔너리 : 시간 복잡도 O(1)
N = int(input())

# 입력 값 중복 제거 및 정렬
lst = list(map(int, input().split()))
num = list(set(lst))
num.sort()

# 딕셔너리를 활용하여 인덱스(value 값) 부여
num_dict = {}
for i in range(len(num)):
    num_dict[num[i]] = i

# 중복 제거 및 정렬한 입력값의 value 값 출력
for j in lst:
    print(num_dict[j], end = ' ')

 

 

사실, 딕셔너리를 활용하지 않고 '리스트.index()'를 활용하여 코드를 짜보았는데, 시간초과가 나왔다.

리스트.index()의 시간복잡도는 O(n)인 반면, 딕셔너리의 시간 복잡도는 O(1)이기에 딕셔너리를 사용하면 시간이 줄어든다.

# 시간초과 (리스트.index(i) : 시간 복잡도 O(n))
N = int(input())

lst = list(map(int, input().split()))
num = list(set(lst))
num.sort()

new_num = []

for i in lst:
    new_num.append(num.index(i))
print(*new_num, sep = ' ')

 

 

 

3. 참고 포스팅

코딩테스트 준비 - 백준18870번 좌표압축 풀이:파이썬 딕셔너리 활용 (파이썬)

 

[백준] 18870 좌표 압축 (Python 파이썬)

 

 

[+] 시간 복잡도 관련 포스팅

[Python] 파이썬 자료형 및 연산자의 시간 복잡도(Big-O) 총 정리