[JS] 프로그래머스 - 가장 큰 수(레벨 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 합니다.

입출력 예

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

 

나의 풀이

처음 이 문제를 보자마자 숫자 데이터를 문자열로 바꾸고 아스키코드를 이용한 문자 정렬 방식이 떠올랐다. 오늘은 생각보다 문제를 빨리 풀겠구나 싶었는데 역시 레벨2 문제라 그렇게 쉽게 풀릴리가 없었다.

고작 3 ~ 4 개 정도의 테스트 케이스만 통과할 뿐이었다. 골칫덩이였던 부분은 예를 들어 [6, 5, 50]이란 배열이 있는데 문자 정렬 방식을 이용하여 구한 가장 큰 수는 6505였다. 하지만 실제로 가장 큰 수는 6550이다.

이 5와 50이라는 숫자를 어떻게 정렬시킬 수 있을까? 에 대해 생각하며 오만가지 방법을 가져다가 시도해보았지만, 아직 내 수준이 이 정도에 못 미친다는 것을 알았다. 

그래서 어쩔 수 없이 다른 사람들의 풀이를 보며 이 문제는 어떻게 풀 수 있는지 알게 되었다. 

 

크게 두 가지 방법으로 이 문제를 풀 수 있다.

 

첫번째 방법은 정렬을 진행하면서 두 수의 앞 뒤 자리를 바꿔가며 비교하는 것이다. 예를 들어 "5"와 "50"이 있을 때  "505"와 "550"를 만들어서 두 값을 비교한다. ("50" + "5") - ("5" + "50") < 0이므로 sort 함수에게 음수 값이 전달되어 두 요소는 현재 위치를 그대로 유지한다. 이러한 방식으로 다른 요소들 또한 정렬이 이루어진 후 모든 요소를 이어붙이게 되면 가장 큰 수를 구할 수 있다.

 

function solution(numbers) {
  let answer = '';
  numbers = numbers.map((v) => v + "").sort((a, b) => (b+a) - (a+b));
  // numbers가 [0,0,0,0,...]인 경우
  // 이때는 0이 가장 큰 수이다.
  answer = numbers[0] === '0' ? '0' : numbers.join('');
  return answer;
}

 

두번째 방법은 모든 요소들을 네 자리 수로 만들어서 비교하는 것이다. 제한 사항을 보면 numbers의 원소는 0 이상 1000 이하의 정수이다. 최대 값이 1000인 네 자리 수이기 때문에 네 자리 수를 만들어야 한다. 이 네 자리 수는 오로지 요소들이 기존에 가지고 있는 값만으로 이루어져 있다.

예를 들어 [6, 10, 2]를 입력으로 받는다면, 이들의 네 자리 수는 [6666, 1010, 2222]가 되고 이들을 내림차순으로 정렬하면 [6666, 2222, 1010]이 된다. 이 네 자리 수의 원래 값은 [6, 2, 10]이므로 이들을 이어붙여 문자열로 변환하면 "6210" 즉 이 요소들로 만들 수 있는 가장 큰 숫자가 된다.

 

function solution(numbers) {
  let result = [];
  // 모든 요소들을 네 자리 수로 
  for (let i = 0; i < numbers.length; i++) {
    const number = String(numbers[i]);
    const numberLength = number.length;
    let tempNumber = number;
    let j = 0;
    
    // 요소가 네 자리 수가 될 때까지 진행된다.
    while (tempNumber.length <= 3) {
      tempNumber = tempNumber + number[j];
      j = (j+1) % numberLength;
    }
    // 각각 네 자리 수와 원본 요소를 객체의 형태로
    result.push({'converted': tempNumber, 'original': number});
  }

  // 네 자리 수들을 내림차순으로 비교
  result.sort((a, b) => b.converted - a.converted);
  // 원본 요소들을 이어붙인다.
  const answer = result.map((v) => v.original).join('');
  
  // answer이 "000..."인 경우는 0이 가장 큰 수이다.
  return answer[0] === '0' ? '0' : answer;
}

 

풀이 출처 : 하나씩 점을 찍어 나가며 님의 티스토리 - [프로그래머스] 가장 큰 수 

        조씨의 개발 블로그 티스토리 - [JavaScript] 프로그래머스 - 가장 큰 수

문제 출처 : 프로그래머스[Level2] - 가장 큰 수