[프로그래머스] 정수 내림차순으로 배치하기 - 배열(지수정렬)

문제 설명

 

문제 풀이

function solution(n) {
    // n을 문자열로 변환하여 각 자릿수를 배열로 만들기
    const digits = n.toString().split('');

    // 각 자릿수를 카운트하기 위한 배열 (0~9)
    const count = new Array(10).fill(0);

    // 각 자릿수의 개수 세기
    for (let digit of digits) {
        count[Number(digit)]++;
    }

    // 결과를 저장할 배열
    let answer = '';

    // 큰 수부터 작은 수로 구성
    for (let i = 9; i >= 0; i--) {
        while (count[i] > 0) {
            answer += i;  // i를 answer에 추가
            count[i]--;   // 카운트 감소
        }
    }

    return parseInt(answer);  // 문자열을 정수로 변환하여 반환
}

 

비교

function solution(n) {
    // n을 문자열로 변환하여 각 자릿수를 배열로 만들기
    const digits = n.toString().split('');

    // 배열을 내림차순으로 정렬
    digits.sort((a, b) => b - a);

    // 정렬된 배열을 다시 문자열로 결합하여 정수로 변환
    return parseInt(digits.join(''));
}

 

두 코드 비교

1. 카운팅 배열을 사용하는 코드:
   • 장점:
     • 시간 복잡도가 O(n)입니다. 각 자릿수를 카운트하고, 그 카운트를 기반으로 결과를 만드는 것이므로, 입력 숫자의 길이에 비례하여 효율적입니다.
     • 공간 복잡도가 O(1)입니다. 고정된 크기(0-9)의 배열을 사용하기 때문입니다.
   • 단점:
     • 코드가 조금 더 길고 복잡할 수 있습니다.
2. sort() 메서드를 사용하는 코드:
   • 장점:
     • 코드가 간결하고 이해하기 쉽습니다. 자바스크립트의 내장 메서드를 활용하기 때문에 코드가 더 직관적입니다.
   • 단점:
     • 평균적으로 O(n log n)의 시간 복잡도를 가집니다. 정렬 과정에서 사용되는 비교 작업이 많기 때문입니다.
     • 공간 복잡도가 O(n)입니다. 배열을 생성하고 정렬하는 과정에서 추가적인 메모리를 사용합니다.

결론

• 성능 측면: 입력의 크기가 크고 자릿수 범위가 한정되어 있는 경우(0-9), 카운팅 배열을 사용하는 방법이 더 효율적입니다. 이 경우 O(n)의 시간 복잡도를 가지므로, 처리 속도가 빠릅니다.
• 코드의 간결성: 코드가 간결하고 빠른 프로토타입을 원한다면 sort() 메서드를 사용하는 방법이 더 좋습니다. 다만, 입력 크기가 커지면 성능 저하를 경험할 수 있습니다.