Algorithm | 가장 큰 수

프로그래머스 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 합니다.

예시

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

📍1차 시도

function solution(numbers) {
    var answer = '';
    answer = numbers.sort().reverse().join('');
    return answer;
}

sort()는 compareFunction 가 주어지지 않으면 각 인덱스의 제일 처음에 위치한 값을 통해 비교하여 오름차순으로 정리한다.(6과 10이 있으면 오름차순으로 정리하면 10이 더 작은 값으로 간주됨.)

가장 큰 수를 만들기 위해서는 numbers의 각 인덱스별 값 중 더 큰 자리값에 큰 수가 배치되어야한다.
(6과 200이 있어도 6이 더 낮은 색인, 즉 먼저 배치되어야한다는 말)

그 말은 큰 자리수에 더 큰 숫자를 오게하려면 numbers배열의 요소들을 내림차순으로 배치하여 하나로 묶으면 된다고 생각해서

answer = numbers.sort().reverse().join('');

와 같은 코드를 작성하였다.

• 문제는 numbers의 각 요소의 첫 값이 같을 때 큰 자리수에 큰 수를 위치시킬 수 없다는 것이다.
  (30과3이 있으면 303 보다는 330이 크지만! 303순으로 배치됨)

- 즉, 두 요소의 조합을 비교해야한다.

📍2차 시도

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

정렬을 할 때 sort()함수를 사용한다. compareFunction은 인자로 a,b를 받는데 그 return값에 따라서 a,b의 대소를 비교한다.

🌟 포인트

여기서 중요한 것은 a,b를 비교할때 return값이 0보다 작으면 a가 먼저 온다는 것이다.
a가 먼저 온다는 말은 a,b 두 값의 인덱스가 바뀌지 않는 것, ✅그대로 라는 것이다.

자, arr = ["3","30"] 이 있다. a+b = "330", b+a="303"이다.
sort함수의 compareFunction내에서 a+b가 크면 arr내의 a,b의 인덱스는 그대로여야한다.
즉, return값이 -가 나와야한다.
그래서 a+b가 클 경우 음수를 return하려면 "작은수 - 큰수" = "(b+a)-(a+b)"를 해주어야한다.

🌟 다시 정리하면
a,b가 바뀌지 않기 위해서는 return값이 음수라는 것이고,
a,b가 바뀌지 않을때는 a+b>b+a 라는 것이다.
a+b>b+a 인 상황에서 return값이 음수이기 위해서는 "(b+a)-(a+b)"를 해주어야한다.

이처럼 상황에 맞게 compareFunction 내에서 실행될 코드를 작성해주면 된다.

?!? 당연히 통과할 줄 알았는데 테스트케이스 11에서 실패했다. 어떤 예외처리를 해주어야 하는 것 같다.

📍 3차 시도

알아보니 제한조건이 "numbers의 원소는 0 이상 1,000 이하입니다." 였기 때문에 모든 요소가 0인 배열이 인자로 주어질 수 있고 이때는 return 값이 숫자 0이 아닌 00000이 리턴된다.

따라서 [0,0,0,0,0]과 같은 모든 요소가 0인 배열에 대한 예외 처리를 해주어야한다.

function solution(numbers) {
    let answer = [];
    answer = numbers.sort((a,b)=> (""+b+a)-(""+a+b));
    if(answer.every((num)=> num === 0)){
      answer = [0];
    }
    return answer.join('');
}

answer을 2차 시도때 처럼 string이 아닌 array로 만들고, every함수로 answer배열의 모든 요소가 0일때는 true를 반환하게하고, 이때 if문을 통과하게 하였다.

그러면 answer은 [0]으로 0을 가진 배열로 바꾸고 이를 다시 string으로 바꾸어서 리턴하였다.

다른 풀이 #1

(string변환, 예외처리)

function solution(numbers) {
    var answer = numbers.map(v=>v+'')
                        .sort((a,b) => (b+a)*1 - (a+b)*1)
                        .join('');

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

• 다른점

  • 해당 풀이에서는 numbers의 요소를 map함수로 다 string으로 바꾼 후에 진행하였고 나는 sort()내에서 a+b와 b+a의 값을 구할때에 string으로 바꾸어서 계산하였다.

  • 0에 대한 예외처리를 나는 answer배열이 모두 0일때 answer을 0하나를 가지는 배열로 바꾸어 예외처리를 하였지만, 해당 풀이에서는 numbers가 모두0인 배열로 주어진다면 어차피 answer의 첫 인덱스가 0이기 때문에 이를 활용하여 예외처리를 하였다.

예외처리 부분에서는 이 풀이가 훨씬 더 깔끔하고 타당한 것 같다.

다른 풀이#2

(string변환, 예외처리)

function solution(numbers) {
    let answer = numbers.sort((a, b) => `${b}${a}` - `${a}${b}`).join('');
    return answer[0] === '0' ? '0' : answer;
}

• 다른점

  • 이 풀이에서는 템플릿 리터럴을 사용하여 string으로 변환하였다.