[Lv.2] 가장 큰 수

문제 설명

https://school.programmers.co.kr/learn/courses/30/lessons/42746?language=javascript 

프로그래머스

 

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"

 

해결 방법

첫번째 시도

numbers 배열에 들어있는 모든 숫자를 split 하여 내림차순으로 정렬한다.

➡  두 자리 이상 숫자들은 split하지 않고 사용해야 하기 때문에 실패! ❌

 

두번째 시도

numbers 배열 요소 중 가장 긴 길이의 값을 구해서, 모든 요소들의 맨 앞에 있는 값부터 비교하여 정렬하기

➡ 가장 긴 길이의 값으로 while문을 돌면 모든 numbers 요소에 접근을 또 다시 해야 하기 때문에 for문이 들어가서 이중 for문이 생성된다. 또한, 첫번째 인덱스 값들만 비교하는 방법은 코드가 너무 난잡해졌다. 결론적으로 실패.. ❌ 

 

그 다음엔?

다른 방법을 고민하다가 인터넷의 힘을 빌려 힌트를 얻고자 구글링을 하였다.

여러 개의 해결 방법을 보았지만 모든 글들은 다 똑같은 방법으로 문제를 해결하였다. 😕

이 해결 방법은 내가 24시간동안 문제를 붙잡고 있어도 생각해내지 못할 처음 접하는 풀이 방법이였기 때문에, 이 풀이 방법에 대해 조금 더 분석하는 방향으로 결정하였다.

 

해결 코드

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

    return answer[0] === '0' ? '0' : answer;
}

 

코드 분석

분석할 코드는 바로 정렬 코드이다.

arr.sort((a, b) => b + a - (a + b));

기본적으로 sort 함수는 오름차 정렬, 내림차 정렬을 할 때 주로 사용하였지만, 이번 문제에서는 다른 방법의 정렬로 사용되었다.

 

이 풀이는 나의 두 번째 시도와 의도는 비슷하다.

입출력 예시 중 두 번째 예시와 함께 살펴보자.

 

numbers 배열로 들어오는 값이 [3, 30, 34, 5, 9] 이라고 하자.

이때 [9, 5]는 앞자리 수로 들어올 수 있는 명확한 숫자이지만, 문제는 [3, 30, 34] 이다.

이 숫자들 중 어떤 값이 제일 먼저 와야할까?

 

답은 간단하다. 실제로 숫자들을 서로 붙여보고 어떤 숫자가 더 먼저와야 큰 지 정렬을 하는 것이다.

이 때 + 연산자는 정수로서가 아닌 문자열로서 계산한다.

 

(3 + 30) - (30 + 3)

= 330 - 303

➡ 3이 30보다 먼저 와야 숫자가 더 크다.

 

(30 + 34) - ( 34 + 30)

= 3034 - 3430

➡ 34이 30보다 먼저 와야 숫자가 더 크다.

 

(3 + 34) - ( 34 + 3 )

= 334 - 343

➡ 34가 3보다 먼저 와야 숫자가 더 크다.

 

 

이런 식으로 비교가 가능하다. (9와 5는 굳이 식을 적지 않더라도 앞으로 와야 하는 수이기 때문에 생략하였다.)

내가 생각해낸 방식보다 훨씬 코드가 간결해지는 방법이기 때문에, 이번 기회에 공부를 해두고 나중에 비슷한 문제가 출제되었을 때 사용할 생각이다.

 

문제를 통해 배운 점 

sort 함수는 내림차순 정렬, 오름차순 정렬 이외의 용도로 사용할 수 있다.

sort 함수 내부에 들어갈 수 있는 또 다른 로직을 생각해보는 연습을 하자 😁