[프로그래머스 lv2] 가장 큰 수 - 병합 정렬(Merge Sort) 사용한 풀이

문제 설명

0 또는 양의 정수가 주어졌을 때, 정수를 이어 붙여 만들 수 있는 가장 큰 수를 알아내 주세요.

예를 들어, 주어진 정수가 [6, 10, 2]라면 [6102, 6210, 1062, 1026, 2610, 2106]를 만들 수 있고, 이중 가장 큰 수는 6210입니다.

0 또는 양의 정수가 담긴 배열 numbers가 매개변수로 주어질 때, 순서를 재배치하여 만들 수 있는 가장 큰 수를 문자열로 바꾸어 return 하도록 solution 함수를 작성해주세요.

제한 사항

• numbers의 길이는 1 이상 100,000 이하입니다.
• numbers의 원소는 0 이상 1,000 이하입니다.
• 정답이 너무 클 수 있으니 문자열로 바꾸어 return 합니다.

입출력 예

입출력 예

---

나의 풀이

여러 시도를 해보았는데 생각보다 까다로웠던 문제였다.

시도해본 방법으로는

• 가장 긴 숫자를 찾아 그 숫자의 길이만큼 모든 숫자의 뒤에 '9'로 채웠다.
  • '933', '9' 과 비교에서 '9933', '9339' 일 때 '9933'이 더 크기 때문에 '933' < '9' 이다.
  • 비교를 위해 더 긴 숫자인 '933'의 길이(3) 만큼 다른 숫자들 뒤에 '9'를 채우면
  • '933' ,'999'가 된다. 
  • '933', '9' 의 비교에서는 맞는 결과이지만 '34', '3' 과 같은 숫자에서는 '34' > '3' 이지만 뒤에 '9'를 붙이면 '34' < '39' 라서 틀리게 된다.
• 다음 시도한 방법은 '9'로 채우는 것이 아닌 그 숫자의 마지막 숫자로 채웠다.
  • '933', '9'를 비교할 때 '933', '999' 로 위의 경우와 똑같기 때문에 정답이며
  • '34' ,'3'을 비교할 때 '34', '33' 이기 때문에 이 경우에도 정답이 된다.
  • '968', '96'를 비교할 때 '968', '966'를 비교하면 '968'이 더 커야하지만
    • 실제로는   '96896' > '96968'이라서 '968' < '96' 이기 때문에 틀리게 된다.
• 예외 케이스가 잘 안떠오르고 적당한 조건이 떠오르지 않아서 파이썬의 sorted 메소드가 아닌 직접 정렬 알고리즘으로 구현하려고 했다.
• 그래서 선택한 정렬 방법이 Merge Sort이다.
  • Merge Sort는 O(nlogn) 의 복잡도를 가지는 대표적인 분할 정복 알고리즘의 예이다.
  • 퀵 정렬, 힙 정렬 등의 효율적인 정렬 방법과 견주는 시간 복잡도를 갖는다.
  • 참고로 파이썬의 sort / sorted 정렬 메소드에서는 Tim sort를 사용하는 것으로 알려져 있는데, Tim sort는 (여기서 사용한) 병합 정렬과 삽입 정렬을 적절히 섞은 알고리즘이라고 하며 시간복잡도는 마찬가지로 O(nlogn) 이라고 한다. (추가로, sort는 파이썬이 아닌 'C'언어로 작성되었다.)

(참고) 파이썬의 sort에 대한 공식 문서

(https://raw.githubusercontent.com/python/cpython/ba18c0b13ba3c08077ea3db6658328523823a33f/Objects/listsort.txt)

 

(C) Linked List로 작성된 MergeSort

2021.03.15 - [C] linked list를 활용한 Merge Sort

[C] linked list를 활용한 Merge Sort

 

소스 코드

def solution(numbers):
    numbers = [str(x) for x in numbers]
    answer = ''.join(mergeSort(0, len(numbers), numbers))
    return '0' if answer[0] == '0' else answer

def mergeSort(start, end, arr):
    if start+1 >= end: return arr[start:end] # 종료조건. 숫자 하나짜리 리스트는 그대로 반환
    arr1 = mergeSort(start, (start+end)//2, arr)
    arr2 = mergeSort((start+end)//2, end, arr)
    i1, i2 = 0, 0 # arr1, arr2의 인덱스
    merged = [] # 병합 후 리턴 될 결과
    while i1<len(arr1) and i2<len(arr2): # arr1과 arr2에 비교할 값이 있으면 반복
        num1, num2 = arr1[i1], arr2[i2]
        if int(num1+num2) > int(num2+num1): # 두 값 비교. num1 > num2
            merged.append(num1)
            i1 += 1
        else:
            merged.append(num2)
            i2 += 1
    if i1<len(arr1): merged.extend(arr1[i1:]) # arr1 값이 남았으면 뒤에 추가
    if i2<len(arr2): merged.extend(arr2[i2:]) # arr2 값이 남았으면 뒤에 추가
    return merged

merge sort 과정

• 주어진 리스트를 숫자가 하나 남을 때까지 재귀적으로 반으로 쪼갠다. (분할)
• 쪼개진 왼쪽, 오른쪽 리스트를 기준에 맞춰 정렬한다. (정복)
• 쪼개진 두 리스트를 하나의 정렬된 리스트로 합병한다. (결합)

글보다 위의 애니메이션을 통한 이해가 훨씬 빠를 것이다.

merge sort에도 다양한 방법이 있기 때문에 관심이 있는 사람은 더 공부를 하면 좋을 것 같다.

여기서 중요한 것은 정렬 기준이다.

나는 '123' 이라는 숫자와 '345'라는 숫자가 있을 때 '123345', '345123' 이렇게 두 개의 경우를 만들어 직접 비교했다.

int(num1+num2) > int(num2+num1) # num1, num2는 문자열

 

그리고 놓치기 쉬웠던 부분이 입력으로 [0,0,0,0, ..., 0] 이 들어오는 경우이다.

모든 숫자로 0이 들어오게 되면 결과로 '0000..0' 이 아닌 '0'이 되어야 한다.

그래서 int() 로 바꾼 후에 다시 str()으로 바꿀 수도 있지만 정렬 후 '0' 이 가장 앞에 오는 경우는 '0'보다 큰 숫자가 없었다는 의미이기에 '0'을 바로 return 하는 것이 int()로 바꿨다가 다시 str()으로 바꾸는 것보다 더 효율적이다.

테스트 결과