Aidengoldkr – Tech Blog

좌표압축 - 실버 2

문제

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

Xi를 좌표 압축한 결과 X'i의 값은 Xi > Xj를 만족하는 서로 다른 좌표 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

 

풀이과정

정렬 문제인 만큼, 문제를 처음보았을 때 다음과 같이 생각했다. 

• 입력에 주어진 리스트를 복제하고, 복제한 리스트를 정렬한다.
• 오름차순으로 0부터 번호를 매겨 딕셔너리로 저장한다
• 이 때, pre 변수를 두어 같은 수에는 같은 수가 저장되게 한다.
• 딕셔너리의 Key 값으로 Vaule를 찾아 출력한다.

이 구조를 그대로 Python 코드로 구현해보았다.

n = int(input())
points = list(map(int, input().split()))
clone = points.copy()
clone.sort()
sortdict = {}
done = []
nuum = 0
pre = clone[0]
for i in clone:
    if i in done:
        continue
    if i != pre:
        nuum += 1
    sortdict[i] = nuum
    done.append(i)
    pre = i

for i in points:
    print(sortdict[i], end=" ")

 

해당코드는 시간초과로 오답처리 되었다. 중복을 제거하기 위해 done 리스트를 추가로 배치했고 그로 인해 시간복잡도가 O(n²) 가 되어버린다. 

n = int(input())
points = list(map(int, input().split()))
clone = sorted(set(points))
sortdict = {}
nuum = 0
for i in clone:
    sortdict[i] = nuum
    nuum += 1

for i in points:
    print(sortdict[i], end=" ")

이 코드가 정답코드이다. 중복을 제거하면, 앞 수가 같은 수 인지 판별할 필요가 없기에 해당 로직을 삭제하고 중복제거는 done 리스트가 아닌 clone = sorted(set(points))로 정렬과 복제를 한 번에 수행했다. 이로 인해 시간복잡도가 O(n log n) 이 되어 정답이 된다.