[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"

 

 

나의 풀이

 제한사항을 보니, numbers의 최대 길이는 100,000이다. 분명히 순열을 써서 정렬하면 시간초과가 남발하는 결과를 보게 될 것이다.

물론 자의적으로 풀지는 못했다. 몇 시간이나 고민했는데 아직 내 실력으로는 이 문제를 자의적으로 풀 수 있는 레벨에 못미친다는 것을 알았다. 

 

 

 그런 이유로 다른 사람의 풀이를 봤다. 크게 두 가지 방법이 있었다.

 

 

첫째, 정렬을 진행하면서 두 수의 앞 뒤 자리를 바꿔가며 비교한다. 무슨 말이냐면 예를 들어 "6"과 "10"이 있을때 "610"과 "106"을 만들어서 두 값을 비교 후 최대 값을 리턴해서 넣다보면 "6210"을 출력할 수 있다.

 

function solution(numbers) {
    var answer = '';
    numbers = numbers.map((v) => v + "").sort((a,b) => (b+a) - (a+b));
    /* 테스트케이스 11: "0000"의 경우 0으로 변환시켜줘야 한다. */
    numbers[0] === '0' ? answer += 0 : answer = 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 answer = [];
  for(let i=0; i<numbers.length; i++){
    const item = numbers[i];
    const itemLength = String(item).length;
    let tempNum = '' + numbers[i];
    let j = 0;

    while(tempNum.length <= 3){
      tempNum = tempNum + tempNum[j];
      j = (j+1)%itemLength;
    }
    answer.push({'compare': tempNum, 'original': item});
  }
  
  answer.sort((a,b) => b.compare*1 - a.compare*1);
  const answerNum = answer.map((v) => v.original).join("");
  
  return answerNum[0] === 0 ? '0' : answerNum;
}

 

 

참고자료

 1. 하나씩 점을 찍어가며님의 티스토리 - [프로그래머스] 가장 큰 수

 2. 글 쓰는 공돌이 - 프로그래머스 고득점 Kit: 가장 큰 수