프로그래머스/Lv.2/가장 큰 수

 

문제 설명

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"
[1, 10, 100, 1000, 818, 81, 898, 89, 0, 0]	"8989881881110100100000"

---

정렬 하는 방법을 1시간 넘게 정렬 매커니즘을 고민했지만 문제를 제출할 때 계속 많은 에러가 발생했습니다.

그러던 중 다른 곳에서 힌트를 얻어 정말 간단하고 빠른 풀이가 나왔습니다.

 

논리는 간단합니다. 숫자 A 와 B가 주어진다면 단순히 AB BA 의 크기를 비교 하면 됩니다.

[6, 10, 2] =(610>106)=> [6, 10, 2] =(102<210)=> [6, 2, 10]

function solution(numbers) {
    numbers = numbers.map( el => el.toString() );
    numbers.sort((a, b) => Number(b + a) - Number(a + b), console.log(a+b));
    return numbers[0] !== '0' ? numbers.join('') : '0';
}

처음 이 풀이를 보면 내부에서 어떻게 돌아가는 것인가 햇갈릴 수 있습니다.

그럴 때는 별개의 함수로 정렬 로직을 분리해서 console.log()를 찍어주면 편합니다.

function test(a, b) {
	Number(b + a) > Number(a + b) ? console.log('InnerValue', b + a + '>' + a + b) : console.log('InnerValue', b + a + '<' + a + b);
	Number(b + a) > Number(a + b)
		? console.log('InnerResult', '[' + b + ',' + a + ']=>[' + b + ',' + a + ']')
		: console.log('InnerResult', '[' + b + ',' + a + ']=>[' + a + ',' + b + ']');
	return Number(b + a) - Number(a + b);
}
function solution(numbers) {
	numbers = numbers.map((el) => el.toString());
	numbers.sort((a, b) => test(a, b));
	return numbers[0] !== '0' ? numbers.join('') : '0';
}

console.log('Result', solution([3, 30, 34, 5, 9]));

 이렇게 세팅을 하고 정렬 메소드 내부에서 어떤 일이 벌어지고 있는지 보겠습니다.

InnerValue 330>303
InnerResult [3,30]=>[3,30]

InnerValue 3034<3430
InnerResult [30,34]=>[34,30]

InnerValue 3034<3430
InnerResult [30,34]=>[34,30]

InnerValue 334<343
InnerResult [3,34]=>[34,3]

InnerValue 35<53
InnerResult [3,5]=>[5,3]

InnerValue 345<534
InnerResult [34,5]=>[5,34]

InnerValue 39<93
InnerResult [3,9]=>[9,3]

InnerValue 349<934
InnerResult [34,9]=>[9,34]

InnerValue 59<95
InnerResult [5,9]=>[9,5]

Result 9534330

정렬 코드 내부에서는 이런 방식으로 작동합니다.

이를 시각화 하면

[3, 30, 34, 5, 9]
=> (3과 30 비교) => [3, 30, 34, 5, 9] 
=> (30과 34 비교) => [3, 30, 34, 5, 9]
=> (34와 5 비교) => [3, 30, 5, 34, 9] 
=> (30과 5 비교) => [3, 5, 30, 34, 9] 
=> (3과 5 비교) => [3, 5, 30, 34, 9]
=> (30과 9 비교) => [3, 5, 9, 30, 34] 
=> (5와 9 비교) => [3, 5, 9, 30, 34]

향후 다른 정렬 문제에서도 내부를 이런 방식으로 시각화하여 관찰하면 쉽게 이해 할 수 있습니다.

※자바스크립트는 자체적인 커스텀 정렬 알고리즘을 사용하기 때문에 우리가 알고 있는 일반적인 정렬 알고리즘과는 약간의 차이가 있습니다.