알고리즘 풀이: [프로그래머스] 가장 큰 수

https://programmers.co.kr/learn/courses/30/lessons/42746

코딩테스트 연습 - 가장 큰 수

 

문제 설명

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

 

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

 

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

 

제한 사항

numbers의 길이는 1 이상 100,000 이하입니다.

 

numbers의 원소는 0 이상 1,000 아히압니다.

 

정답이 너무 클 수 있으니 문자열로 바꾸어 return 합니다.

 

 

입출력 예

numbers	return
[6, 10, 2]	"6210"
[3, 30, 34, 5, 9]	"9534330"
[3, 30, 34, 5, 9, 3]	"95343330"
[20, 200, 20]	"2020200"
[0, 0, 0, 1000]	"1000000"
[12, 121]	"12121"
[21, 212]	"21221"
[70, 0, 0, 0]	"70000"
[12, 1213]	"121312"

 

---

문제 풀이

입력으로 제공된 numbers를 "기준"에 따라서 정렬한 이후에 join() 메서드를 사용해서 하나의 문자열로 이어 붙이다.

 

 

numbers를 정렬하는 기준을 다음과 같다.

숫자 A와 숫자 B가 있을 때 AB를 이어 붙인 숫자와 BA를 이어 붙인 숫자를 비교한다. 이어 붙인 숫자가 더 큰 순서대로 A와 B를 정렬한다.

정렬 예시(왼쪽: A=6, B=10 오른쪽: A=30, B=303)

A가 6이고 B가 10이라고 가정하자. AB 순으로 이어 붙인 숫자는 610이고 BA 순으로 이어 붙인 숫자는 106이다. AB(610)가 BA(106) 보다 크므로 A(6)와 B(10)를 정렬한다면 A(6), B(10) 순서가 된다.

 

마찬가지로 A가 30이고 B가 303인 상황을 가정하자. 이러한 경우 AB는 30303, BA는 30330이므로 BA(30330)가 AB(30303) 보다 크다. 따라서 B(303), A(30) 순으로 정렬한다. 

 

numbers를 정렬하는 알고리즘은 병합 정렬을 사용한다.

병합 정렬은 재귀 함수로 구현하며 정렬할 대상을 "분할"하고 "병합"하는 과정으로 구분한다.

 

"분할" 과정은 정렬 대상이 되는 리스트를 절반씩 부분 리스트로 나누는 과정이다. 분할된 각 부분 리스트는 재귀적으로 병합 정렬을 사용해서 정렬한다. 만약 부분 리스트의 원소의 개수가 1개나 0개라면 해당 부분 리스트는 정렬이 완료되었다고 가정하고 가정하고 더 이상 분할하지 않는다.

 

부분 리스트 [34]와 부분 리스트 [9, 5]의 병합 과정

"병합" 과정은 재귀적으로 병합 정렬된 두 부분 리스트를 하나의 정렬된 리스트로 병합하여 반환하는 과정이다. 두 부분 리스트 L1, L2를 하나의 리스트로 병합하여 정렬하기 위해서 (리스트 L1의 크기 + 리스트 L2의 크기)인 새로운 리스트 L3를 정의한다. 새로운 리스트는 두 부분 리스트를 병합하여 정렬한 리스트로서 L1와 L2의 원소를 하나씩 비교하면서 앞 순서의 원소가 L3에 채워진다.  

 

분할과 병합으로 구성된 전체적인 병합 정렬의 과정은 다음과 같다.

 

[3, 30, 34, 5, 9]를 병합 정렬한 결과 [9, 5, 34, 3, 30]이 된다. 이를 하나의 문자열로 합치면 "9534330"이 된다.

 

소스 코드

정렬 기준 함수

def compare(a, b):
    return int(a + b) - int(b + a)

 

병합 정렬 함수

def merge_sort(numbers):
    if len(numbers) <= 1:
        return numbers

    idx = len(numbers) // 2

    l1 = merge_sort(numbers[:idx])
    l2 = merge_sort(numbers[idx:])

    l3 = list()

    idx = 0
    jdx = 0

    while idx < len(l1) and jdx < len(l2):
        a = l1[idx]
        b = l2[jdx]

        if compare(a, b) > 0:
            l3.append(a)
            idx += 1
        else:
            l3.append(b)
            jdx += 1

    while idx < len(l1):
        l3.append(l1[idx])
        idx += 1

    while jdx < len(l2):
        l3.append(l2[jdx])
        jdx += 1

    return l3

 

메인 솔루션 함수

def solution(numbers):
    numbers = [str(num) for num in numbers]
    numbers = merge_sort(numbers)
    return ''.join(numbers) if not numbers[0] == '0' else '0'

 

문제 해결 화면

 

github 주소: https://github.com/dhsong95/-PRACTICE-Programmers-Algorithm/blob/master/level%202/%EA%B0%80%EC%9E%A5%20%ED%81%B0%20%EC%88%98.py

dhsong95/-PRACTICE-Programmers-Algorithm