코딩테스트 정렬 문제 가장 큰 수 만들기, 문제 해결과 코드 리팩토링

코딩테스트 정렬 문제 가장 큰 수 만들기, 문제 해결과 코드 리팩토링

 

 

프로그래머스

 

문제 소개

주어진 배열의 숫자들을 재배치하여 만들 수 있는 가장 큰 수를 문자열 형태로 반환하는 문제입니다. 예를 들어, [3, 30, 34, 5, 9] 배열이 주어졌을 때, 이 숫자들을 재배치하여 만들 수 있는 가장 큰 수는 "9534330"입니다.

 

 

기존 코드의 문제점

기존 작성한 코드는 모든 순열을 생성하여 가장 큰 수를 찾는 방식입니다. 이 방법은 이론적으로는 정확하지만, 실제로는 몇 가지 큰 문제점을 가지고 있습니다.

 

const getPermutations = function (arr, selectNumber) {
    const results = [];
    if (selectNumber === 1) return arr.map((el) => [el]); 
    // n개중에서 1개 선택할 때(nP1), 바로 모든 배열의 원소 return. 1개선택이므로 순서가 의미없음.

    arr.forEach((fixed, index, origin) => {
      const rest = [...origin.slice(0, index), ...origin.slice(index+1)] 
      // 해당하는 fixed를 제외한 나머지 배열 
      const permutations = getPermutations(rest, selectNumber - 1); 
      // 나머지에 대해서 순열을 구한다.
      const attached = permutations.map((el) => [fixed, ...el]); 
      //  돌아온 순열에 떼 놓은(fixed) 값 붙이기

      results.push(...attached); 
      // 배열 spread syntax 로 모두다 push
    });

    return results; // 결과 담긴 results return
}

function solution(numbers) {

    arr = getPermutations(numbers,numbers.length);

    arr.forEach((x,i)=>{
        arr[i] = Number(x.reduce((prev,cur) => ''+prev+cur));
    });

    return Math.max(...arr)+'' ;
}

console.log(solution([3, 30, 34, 5, 9]));

 

효율성: 순열을 생성하는 과정은 매우 비효율적입니다. 배열의 길이가 n일 때, 생성되는 순열의 수는 n!입니다. 따라서, 배열의 크기가 조금만 커져도 계산할 수 없을 정도로 많은 순열이 생성되며, 이는 곧 런타임 에러로 이어집니다.

 

데이터 타입의 한계: 숫자를 문자열로 변환하여 비교하는 과정 없이 숫자로만 처리하려 하면, JavaScript에서 처리할 수 있는 정수의 범위를 초과할 수 있습니다. 이는 결과가 부정확해지거나 오류가 발생할 수 있음을 의미합니다.

 

 

코드 리팩토링

문제를 해결하기 위한 효율적인 방법은 숫자들을 문자열로 변환한 뒤, 문자열 비교를 통해 정렬하는 것입니다. 문자열 비교는 사전 순으로 이루어지므로, 두 문자열 a와 b를 이어 붙였을 때 더 큰 조합을 만들 수 있는 순으로 정렬할 수 있습니다.

 

function solution(numbers) {
    const answer = numbers.map(n => n.toString()) // 숫자를 문자열로 변환
                          .sort((a, b) => (b+a) - (a+b)) // 문자열을 이어붙인 결과를 비교하여 정렬
                          .join(''); // 정렬된 문자열을 이어붙임

    // 모든 숫자가 0일 경우 "0"을 반환해야 하므로, 첫 번째 문자가 "0"인지 확인
    return answer[0] === '0' ? '0' : answer;
}

 

 

리팩토링된 코드의 장점

효율성: 순열을 모두 생성하고 그 중 가장 큰 값을 찾는 대신, 문자열 비교를 통해 한 번의 정렬로 문제를 해결할 수 있습니다. 이 방법은 시간 복잡도를 대폭 줄여줍니다.

 

정확성: 숫자의 범위를 넘어서는 큰 수도 문자열로 처리하기 때문에, 정확한 비교가 가능합니다.

 

간결성: 코드가 더 짧고 이해하기 쉬워집니다.

 

---

 

이러한 방법으로 문제를 해결하면, 런타임 에러 없이 주어진 입력 값으로 만들 수 있는 가장 큰 수를 효율적으로 찾아낼 수 있습니다.

 

▼ 아래 문제도 풀어보세요! ▼

 

코딩테스트 최소 힙(MinHeap)을 활용한 "더 맵게" 문제 해결법

 

코딩테스트 큐(queue) 문제 - 기능개발 풀이 과정 및 코드 리팩토링