[백준] 18870 좌표 압축

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

메모리 제한도 512MB에 시간도 널널해서 쉽게 풀 줄 알았는데 30분 정도 고전했다ㅜㅜ
사실 처음에 시간초과 낸 알고리즘에서 수정된 건 하나밖에 없다.

1. 정렬로 시간복잡도 O(nlogn) + 정렬 시에 중복제거까지 동시에
2. 딕셔너리를 사용하여 정렬된 리스트를 한 번 순회하여 O(n) 인덱스를 통하여 좌표 압축

이게 생각한 알고리즘이었는데 딕셔너리 사용은 좋았던 것 같다.
어차피 정렬 제거한 값을 넣을 거라 해쉬 충돌도 없고 값 삽입, 조회 모두 O(1)

하지만 정렬시, 내장 라이브러리를 사용하지 않고 직접 구현하기 때문에 조금 더 조잡할 것이었고 거기에 중복 제거까지 하니 시간초과가 발생했다.

import sys

def mergeSort(array):
    if len(array)<2: return array

    mid=len(array)//2
    left=mergeSort(array[:mid])
    right=mergeSort(array[mid:])

    merged=[]
    l=r=0
    while l<len(left) and r<len(right):

        if len(merged)==0:
            if left[l]<right[r]:
                merged.append(left[l]); l+=1
            elif left[l]==right[r]:
                merged.append(left[l]); l+=1; r+=1
            else:
                merged.append(right[r]); r+=1

            continue

        mergedLast=merged[-1]

        if left[l]<right[r]:
            if mergedLast==left[l]:
                l+=1; continue

            merged.append(left[l]); l+=1

        elif left[l]==right[r]:
            if mergedLast==left[l]:
                l+=1; r+=1; continue

            merged.append(left[l]); l+=1; r+=1

        else:
            if mergedLast==right[r]:
                r+=1; continue

            merged.append(right[r]); r+=1 

    merged+=left[l:];merged+=right[r:]
    return merged

num=int(sys.stdin.readline())
inputStr=sys.stdin.readline().replace("\n","")

inputStrList=inputStr.split()
coordinate=[]

for i in inputStrList:
    coordinate.append(int(i))

sortedCoordinate=mergeSort(coordinate)

coordinateDict=dict()

for c in range(len(sortedCoordinate)):
    coordinateDict[sortedCoordinate[c]]=c


#coordinate, coordinateDict으로 압축 결과 print
for i in coordinate:
    print(coordinateDict[i],end=' ')

✊🏻 그 후 해괴하게 바꾸다가 그냥 set으로 중복 제거를 하는 게 답이라는 생각이 들어 수정

import sys

def mergeSort(array):
    if len(array)<2: return array

    mid=len(array)//2
    left=mergeSort(array[:mid])
    right=mergeSort(array[mid:])
    
    merged=[]
    l=r=0
    while l<len(left) and r<len(right):
        if left[l]<right[r]:
            merged.append(left[l]); l+=1
        else:
            merged.append(right[r]); r+=1

    merged+=left[l:]; merged+=right[r:]

    return merged

num=int(sys.stdin.readline())
inputStr=sys.stdin.readline().replace("\n","")

inputStrList=inputStr.split()
inputCoordinate=[]

for i in inputStrList:
    inputCoordinate.append(int(i))

coordinate=list(set(inputCoordinate))
sortedCoordinate=mergeSort(coordinate)

coordinateDict=dict()
for c in range(len(sortedCoordinate)):
    coordinateDict[sortedCoordinate[c]]=c

#coordinate, coordinateDict으로 압축 결과 print
for i in inputCoordinate:
    print(coordinateDict[i],end=' ')

최종 코드는 위와 같다.
그래서 메모리를 많이 지정해줬나 싶기도 하다.

사실 sorted, sort 쓰면 쉽게 해결될 문제이긴 하나 그게 결론적으로는 도움이 안 되는 것 같아서 현재 스터디에서는 sort 관련은 구현해서 사용하고 있다.