[프로그래머스] 가장 큰 수

문제 요약

0 또는 양의 정수가 담긴 배열이 주어졌을 때 해당 수들을 한번씩만 사용하여 이어 붙여 만들 수 있는 가장 큰 수를 반환하세요.

 

나의 생각

처음에는 DFS를 이용해서 배열에 담긴 모든 요소들을 조합하여 가장 큰 수를 비교하는 방벙으로 구현하였습니다. 그 결과 시간 초과 및 숫자의 길이가 변수에 담을 수 있는 크기를 초과하는 문제가 발생하였습니다.

이를 해결하기 위해 문제의 카테고리에서처럼 정렬 방식으로 구현하도록 변경하였습니다. 두수의 앞뒤를 바꿔가며 이어 붙여 숫자를 만든 후 비교하는 방법을 사용하였습니다. 그리고 정렬이 완료되면 join을 사용하여 하나의 문자열로 만들었습니다.

 

여기에서 가장 주의해야할 점은 배열의 모든 수가 0인 경우입니다. 배열의 길이가 아무리 길어도 모든 요소가 0인 경우라면 반환된 값은 "0"이어야 합니다. 이를 위한 조건만 추가하면 테스트에 통과하게 됩니다.

function solution(numbers) {
  if (numbers.every(n => !n)) {
    return "0";
  }  

  numbers.sort((a, b) => {
    const A = Number(String(b) + String(a));
    const B = Number(String(a) + String(b));

    if (A > B) {
        return 1;
    } else if (B > A) {
        return -1;
    }

    return 0;
  });

  return numbers.join('');
}