[프로그래머스] Lv2 - 가장 큰 수

 

문제 : 가장 큰 수

바로가기

 

문제 설명

0 또는 양의 정수가 주어졌을 때, 정수를 이어 붙여 만들 수 있는 가장 큰 수를 알아내 주세요.
예를 들어, 주어진 정수가 [6, 10, 2]라면 [6102, 6210, 1062, 1026, 2610, 2106]를 만들 수 있고, 이중 가장 큰 수는 6210입니다.
0 또는 양의 정수가 담긴 배열 numbers가 매개변수로 주어질 때, 순서를 재배치하여 만들 수 있는 가장 큰 수를 문자열로 바꾸어 return 하도록 solution 함수를 작성해주세요.

 

제한 조건

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

 

입출력 예

s	return
[6, 10, 2]	"6210"
[3, 30, 34, 5, 9]	"9534330"

 

해답 및 해설

풀기 어려웠던 문제였다.

파이썬 (Python)

1. 숫자 문자열을 3번 반복시킨 후 비교
2. 숫자를 합쳐 크기 비교하기

 

숫자 문자열을 3번 반복시킨 후 비교

def solution(numbers):
    numbers = list(map(str, numbers))
    numbers.sort(key = lambda x : x*3, reverse=True)

    answer = str(int((''.join(numbers))))
    return answer

파이썬에서는 숫자를 부등호로 비교를 하면, 앞에서부터 각 자리의 ascii 값을 비교해 Boolean으로 리턴해준다. 그럼 3을 곱해주는 이유는?

 

7, 771

67, 677, 676

 

다음과 같이 두 수간 자리수가 다른 경우를 비교하기 위해서다. 곱하기 3을 하는 이유는 입력 수의 범위가 최대 3자리 수이기 때문이다. 

 

숫자를 합쳐 크기 비교하기

import functools

def comparator(a,b):
    t1 = a+b
    t2 = b+a
    return int(t1) - int(t2)

def solution(numbers):
    n = [str(x) for x in numbers]
    n = sorted(n, key=functools.cmp_to_key(comparator),reverse=True)
    answer = str(int(''.join(n)))
    return answer

두 수를 이어붙인 다음, 어떻게 붙이는게 더 큰지를 확인한다. 자바스크립트의 sort() 함수와 사용 방식이 비슷한 것 같다. functools.cmp_to_key에 대해서 나중에 더 자세히 알아보자.

 

자바스크립트(Javascript)

function solution(numbers) {
    numbers = numbers.map(String);
    numbers.sort((a, b)=>+(b+a)-(+(a+b)));

    var answer = numbers.join('').replace(/^0+/g, 0);
    
    return answer;
}

 파이썬에서 한 방식 중 아래에 있는 방식으로 실행하였다. 그리고 [0, 0, 0, 0]와 같은 엣지 케이스를 위해 문자열 맨 앞쪽에 연속되는 0이 있을 경우 0으로 바꿔주도록 했다.