[프로그래머스] level.2 가장 큰수 😱

 

프로그래머스

 

---

나의 풀이 

 

틀린 풀이

 

처음 생각은 아 모든 numbers를 조합해서 배열로 만든 뒤 Math.max()로 가장 큰 수를 찾아야 겠다.

했는데  

numbers의 길이가 100,000이라고 한다면  경우의 수는 100,000! 이고 1억 아니 1경 아니 1해 아니 1000해도 가뿐이 넘기는 숫자라서 계산이 불가능하다. 

하지만 dfs도 복습할겸 해서 테스트 케이스만 통과하는 코드를 만들어 보았다. 

그러나 생각보다 코드가 바로 생각나지 않았다.  (복습이 필요할 것 같다)

 

 

dfs를 돌리면 result 배열은 1번 예제에서 아래와 같다. 

result

이중에서 Max 값만 구하면 되지만  numbers의 길이가 엄청 길어질 수 있어서 다르게 풀어야한다. 

function solution(numbers){
  const result = [];

  function dfs(arr, prefix = []) {
    if (arr.length === 0) {
         return result.push(prefix.join(""));
    }
      
    for (let i = 0; i < arr.length; i++) {
        const remaining = [...arr.slice(0, i) , ...arr.slice(i + 1)];
        dfs(remaining, [ ...prefix, arr[i]]);
      }
  }
    
  dfs(numbers)  
  return Math.max(...result) + "";
}

 

 

풀이 1)

블로그를 보고 힌트를 얻었다.  

sort를 통해 바로 구할 수 가 있다.  왜 이생각을 못 했을까

또한 sort에 대한 이해가 부족한 것 같아서 다시 정리했다.

function solution(numbers) {
  const answer = numbers
    // 두 개의 숫자를 조합했을 때 더 큰 수가 앞으로 가도록 정렬
    // string으로 더해야 숫자처럼 더해지지않고 옆으로 붙기에 string으로 변경 하고 비교한다.
    .sort((a, b) => b + '' + a - (a + '' + b))
    // 배열을 문자로 변경
    .join('');

  // 0으로만 이루어진 조합 판별
  return answer[0] === '0' ? '0' : answer;
}

 

[JS - 개념] Sort() <배열 고차함수>