[프로그래머스] JavaScript Lv2 - 큰 수 만들기(42883)

개요

문제 이름: 큰 수 만들기 (42883)
문제 링크: https://school.programmers.co.kr/learn/courses/30/lessons/42883
플랫폼: 프로그래머스
알고리즘 분류: 탐욕법(Greedy)
소요 시간: 30분

 

문제 전문

설명

제한사항

입출력

 

문제 풀이

해설

이 문제는 "큰 수 만들기" 문제로, 주어진 숫자에서 특정 개수의 숫자를 제거하여 가장 큰 수를 만드는 것이 목표입니다.

이 문제를 해결하기 위해서는 그리디(Greedy) 알고리즘과 스택(Stack) 자료구조를 활용하는 것이 효과적입니다.

 

문제의 핵심은 다음과 같습니다.

1. 주어진 숫자열을 순회하면서, 각 숫자를 검사합니다.
2. 현재 숫자보다 작은 이전 숫자들을 제거합니다. (단, 제거 가능한 횟수 내에서)
3. 최종적으로 남은 숫자들 중 앞에서부터 필요한 만큼을 선택하여 결과를 만듭니다.

이 접근 방식이 효과적인 이유는, 앞자리 숫자가 크면 클수록 전체 숫자가 커지기 때문입니다. 따라서 가능한 한 큰 숫자를 앞쪽에 배치하는 것이 최적의 해를 찾는 방법입니다.

 

시도

1차 시도  (성공)

function solution(number, k) {
    const stack = [];  // 결과를 저장할 스택
    let count = 0;  // 제거한 숫자의 개수

    for (let i = 0; i < number.length; i++) {
        const current = number[i];  // 현재 검사 중인 숫자

        // 현재 숫자보다 작은 숫자들을 스택에서 제거
        while (count < k && stack.length > 0 && stack[stack.length - 1] < current) {
            stack.pop();  // 스택의 top이 현재 숫자보다 작으면 제거
            count++;  // 제거 횟수 증가
        }

        // 스택의 크기가 최종 길이보다 작으면 현재 숫자 추가
        if (stack.length < number.length - k) {
            stack.push(current);
        }
    }

    return stack.join("");  // 스택의 숫자들을 문자열로 합쳐 반환
}

이 코드는 스택을 사용하여 문제를 해결합니다.

• stack 배열을 생성하여 결과를 저장할 공간을 만듭니다.
• count 변수로 제거한 숫자의 개수를 추적합니다.
• 주어진 number 문자열을 순회하면서 각 숫자를 검사합니다.
• 현재 숫자보다 작은 숫자들을 스택에서 제거합니다. 이때 제거 횟수(count)가 k를 초과하지 않도록 합니다.
• 스택의 크기가 최종적으로 필요한 길이보다 작으면 현재 숫자를 스택에 추가합니다.
• 모든 숫자를 처리한 후, 스택에 있는 숫자들을 문자열로 합쳐 반환합니다.

이 방식의 시간 복잡도는 O(n)입니다. 여기서 n은 number의 길이입니다. 각 숫자는 최대 한 번씩만 스택에 추가되고 제거되기 때문입니다. 공간 복잡도는 O(n)으로, 최악의 경우 모든 숫자를 스택에 저장해야 할 수 있기 때문입니다.

 

2차 시도  (성공)

function solution(number, k) {
    const stack = [];  // 결과를 저장할 스택
    for (let num of number) {
        // 현재 숫자보다 작은 숫자들을 스택에서 제거
        while (k > 0 && stack[stack.length - 1] < num) {
            stack.pop();  // 스택의 top이 현재 숫자보다 작으면 제거
            k--;  // 제거 횟수 감소
        }
        stack.push(num);  // 현재 숫자를 스택에 추가
    }
    stack.splice(stack.length - k, k);  // 남은 k개의 숫자를 뒤에서부터 제거
    return stack.join("");  // 스택의 숫자들을 문자열로 합쳐 반환
}

이 두 번째 접근 방식은 첫 번째와 유사하지만, 코드가 더 간결합니다.

1. for...of 루프를 사용하여 number 문자열의 각 숫자를 순회합니다.
2. 스택의 top에 있는 숫자가 현재 숫자보다 작고, 아직 제거할 수 있는 횟수(k)가 남아있다면 계속해서 제거합니다.
3. 현재 숫자를 항상 스택에 추가합니다.
4. 모든 숫자를 처리한 후, 만약 아직 제거해야 할 숫자가 남아있다면(k > 0), 스택의 뒤에서부터 남은 개수만큼 제거합니다.

이 방식의 시간 복잡도도 O(n)입니다. 각 숫자는 최대 한 번씩만 스택에 추가되고 제거되기 때문입니다. 공간 복잡도 역시 O(n)으로, 최악의 경우 모든 숫자를 스택에 저장해야 할 수 있습니다. 두 접근 방식 모두 효과적이지만, 두 번째 방식이 조금 더 간결하고 이해하기 쉽습니다.

사용된 메서드

• pop(): 배열의 마지막 요소를 제거하고 그 요소를 반환합니다.
• push(): 배열의 끝에 하나 이상의 요소를 추가하고, 배열의 새로운 길이를 반환합니다.
• splice(): 배열의 기존 요소를 삭제 또는 교체하거나 새 요소를 추가하여 배열의 내용을 변경합니다.
• join(): 배열의 모든 요소를 연결해 하나의 문자열로 만듭니다.