[프로그래머스] Lv1. 정수 내림차순으로 배치하기

문제

함수 solution은 정수 n을 매개변수로 입력받습니다. n의 각 자릿수를 큰것부터 작은 순으로 정렬한 새로운 정수를 리턴해주세요. 예를들어 n이 118372면 873211을 리턴하면 됩니다.

제한 조건

• n은 1이상 8000000000 이하인 자연수입니다.

나의 풀이:

def solution(n):
    m = list(str(n))
    m.sort(reverse=True)
    res = "".join(m)            
    return int(res)

알고리즘 이론 공부를 한 게 오히려 독이되었던 문제…

버블정렬, 선택정렬, 병합정렬 중에 선택해서 풀어야 하는 줄 알고 열심히 시도해 보았는데 생각보다 훨씬 까다로웠다.

어쩔 수 없이 의사코드로 푸는 과정을 적어본 뒤 사용 가능한 함수를 검색해서 풀었다.

1. 정수 n을 문자열로 변환한다.
2. 변환된 문자열을 리스트로 변환한다.
3. 리스트를 내림차순으로 정렬한다.
4. 정렬된 리스트를 다시 문자열로 변환한다.
5. 문자열을 정수로 변환한다.

이 과정에서 문자열 정렬에 sort() 내장함수 사용이 가능하고, 리스트를 다시 문자열로 바꿀 때 join() 내장함수 사용이 가능하다는 점을 알게되어 문제풀이에 활용하였다.

다른 사람들의 풀이:

1. 병합정렬

def merge(left, right):
    result = []
    while len(left) > 0 or len(right) > 0:
        if len(left) > 0 and len(right) > 0:
            if left[0] >= right[0]:
                result.append(left[0])
                left = left[1:]
            else:
                result.append(right[0])
                right = right[1:]
        elif len(left) > 0:
            result.append(left[0])
            left = left[1:]
        elif len(right) > 0:
            result.append(right[0])
            right = right[1:]
    return result

def mergeSort(arr):
    if len(arr) <= 1:
        return arr
    mid = len(arr) // 2
    left = arr[:mid]
    right = arr[mid:]
    left = mergeSort(left)
    right = mergeSort(right)
    return merge(left, right)

def solution(n):
    arr = list(str(n))
    n = int(''.join(mergeSort(arr)))
    return n

병합정렬을 함수 사용 없이 코드로 정렬한 분이 계셨다! 나는 시도하다가 ‘이렇게 긴 풀이가 정답일리 없어’ 하면서 다른 노선으로 갈아탔는데 이 분이야말로 성실함의 승리가 아닐까 싶다.

2. join()과 sorted() 메서드를 사용한 한줄풀이

def solution(n):
    return int("".join(sorted(list(str(n)), reverse=True)))