[백준 알고리즘] 18870번: 좌표 압축 (파이썬 / Python)

문제

수직선 위에 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

5
2 4 -10 4 -9

예제 출력 1

2 3 0 3 1

예제 입력 2

6
1000 999 1000 999 1000 999

예제 출력 2

1 0 1 0 1 0

---

문제 접근

입력된 수들을, 자신보다 작은 수의 개수로 변환하여 출력하면 되는 문제이다.

2중 for문으로 index를 각각 비교하여 count하거나, 리스트에서 index() 함수를 사용하면 되겠다는 생각이 들었는데, 둘 다 시간초과가 났다.

 

시간초과 코드

import sys

n = int(sys.stdin.readline())
a = list(map(int, sys.stdin.readline().split()))

for i in a:
    count = 0
    for j in set(a):
        if i > j:
            count += 1
    print(count, end = " ")

import sys

n = int(sys.stdin.readline())
a = list(map(int, sys.stdin.readline().split()))

b = sorted(set(a))

for i in a:
    print(b.index(i))

 

시간초과가 난 이유?

1 ≤ N ≤ 1,000,000 라는 제한 조건 때문인 것 같다. N = 1000000일 때 O(N)이 몇 초 정도 걸리는 지 정확히 모르겠는데, 정답 기준에는 못 미치는 것 같다.

2중 for문은 시간복잡도가 O(n^2)이니 당연히 안되는 것이었고, index()로 배열에 접근할 때의 시간복잡도가 O(N)인데 시간초과가 난 것을 보니 O(nlog(n)) 미만으로 구현해야 하는 것 같았다.   * sort()의 시간복잡도: O(nlog(n))

파이썬의 dictionary의 value에 접근하는 시간복잡도는 O(1)이다.

따라서 {숫자 : index} 형태의 dictionary를 구현하였다.

 

정답 코드

import sys

n = int(sys.stdin.readline())
a = list(map(int, sys.stdin.readline().split()))
new_a = sorted(set(a))                                 #a를 set으로 만들고 정렬한, new_a를 생성
dictionary = {new_a[i] : i for i in range(len(new_a))} #딕셔너리에 '숫자 : new_a에서의 인덱스'로 저장

for i in a:                          #기존 a를 돌며
    print(dictionary[i], end = ' ')  #a[i] key에 해당하는 dictionary의 value를 출력

기존 리스트는 유지하고, 기존 리스트를 set으로 만들고 정렬한 새로운 리스트를 생성한다.

집합, 정렬된 새로운 리스트를 기준으로 인덱스를 부여하고, 출력할 때는 기존 리스트를 사용해야 예제 2번과 같은 입력에 알맞은 출력이 나온다.

 

 

---

 

18870번: 좌표 압축