[백준] 18870 : 좌표 압축

정답코드 1 (내장함수 이용)

import sys
input = sys.stdin.readline

N = int(input())
nums = list(map(int, input().split()))
s = set(nums)
s = list(s)
s.sort()
d = {}
for i in range(len(s)):
    d[s[i]]=i
for n in nums:
    print(d[n], end = ' ')

풀이

정렬 문제이지만 python에서 기본적으로 제공하는 sort함수는 이미 최적화되어있기 때문에 사실 별도의 정렬 알고리즘이 필요하지 않다.

정답코드 2 (mergeSort 구현)

def mergeSort(arr):
    if len(arr) == 1:
        return arr
    mid = len(arr)//2
    arr1 = mergeSort(arr[:mid])
    arr2 = mergeSort(arr[mid:])
    # 작 -> 큰
    h1 = 0
    h2 = 0
    merged_arr = []
    while h1 < len(arr1) and h2 < len(arr2):
        if arr1[h1] < arr2[h2]:
            merged_arr.append(arr1[h1])
            h1 += 1
        else:
            merged_arr.append(arr2[h2])
            h2 += 1
    if h1 != len(arr1):
        merged_arr.extend(arr1[h1:])
    else:
        merged_arr.extend(arr2[h2:])
    return merged_arr