[프로그래머스][C++] 큰 수 만들기

큰 수 만들기

문제 링크

큰 수 만들기

분석

주어진 문자열에서 k개의 숫자를 제거하여 만들 수 있는 가장 큰 숫자를 반환하는 문제입니다.

문자열의 숫자 순서는 유지해야 합니다.

가장 큰 자릿수에는 최대한 큰 수가 와야 큰 수를 만들 수 있습니다.

풀이

#include <string>
#include <stack>

using namespace std;

string solution(string number, int k) {
    string answer = "";
    
    // 순서대로 숫자를 저장할 스택
    stack<char> numberStack;
    // 제거한 숫자 개수를 저장
    int kCount = k;
    
    // 숫자 순회
    for (char num : number)
    {
        // 스택이 비어 있지 않고, 제거할 숫자가 남아 있으며, 현재 숫자가 스택의 top보다 큰 경우
        while(!numberStack.empty() && kCount > 0 && numberStack.top() < num)
        {
            numberStack.pop();
            --kCount;
        }
        
        // 항상 스택에 숫자 추가
        numberStack.push(num);
    }
    
    // 스택에 숫자가 많이 추가 된 경우 불필요한 숫자 제거
    while(numberStack.size() > number.length() - k)
    {
        numberStack.pop();
    }
    
    // 스택에 저장된 숫자를 문자열로 저장
    for (int i = 0; i < number.length() - k; ++i)
    {
        answer = numberStack.top() + answer;
        numberStack.pop();
    }
    
    return answer;
}

제거할 수 있는 숫자가 남았다면, 가장 큰 자릿수에는 가장 큰 수가 올 수 있도록 구현했습니다.

number = "4177252841", k = 4를 예시로 숫자를 순회하는 반복문의 실행 순서는 다음과 같습니다.

1. ‘4’ 삽입 -> 스택: [4]
2. ‘1’ 삽입 -> 스택: [4,1]
3. ‘7’ 등장 -> 1 제거 -> 4 제거 -> 스택: [7]
4. ‘7’ 삽입 -> 스택: [7,7]
5. ‘2’ 삽입 -> 스택: [7,7,2]
6. ‘5’ 등장 -> 2 제거 -> 스택: [7,7,5]
7. ‘2’ 삽입 -> 스택: [7,7,5,2]
8. ‘8’ 등장 -> 5 제거 -> 스택: [7,7,8]
9. ‘4’ 삽입 -> 스택: [7,7,8,4]
10. ‘1’ 삽입 -> 스택: [7,7,8,4,1]

다른 예시로, number = "3210", k = 2를 실행할 경우 앞 자릿수 보다 작은 수와 마지막에 삽입되는 수는 제거되지 않아 스택에 3, 2, 1, 0이 들어가게 됩니다.
하지만, 결과 값의 자릿수는 2개이므로 자릿수를 맞춰주기 위해서 뒤에서부터 제거해줍니다.

성능 요약

시간 복잡도는 $O(n)$입니다.

• 숫자를 순회하는 반복문 $O(n)$
• 스택 크기가 큰 경우 제거하는 반복문 $O(k)$
• 최종 문자열을 생성하는 반복문 $O(n)$
• $O(n + k + n)$ (k는 n보다 작음)

공간 복잡도는 $O(n)$입니다.

• 순서대로 숫자를 저장하는 stack<char> numberStack $O(n)$
• 정답 문자열 string answer $O(n)$
• $O(n + n)$

테스트 1 〉 통과 (0.01ms, 4.17MB)
테스트 2 〉 통과 (0.01ms, 4.14MB)
테스트 3 〉 통과 (0.01ms, 4.14MB)
테스트 4 〉 통과 (0.06ms, 4.2MB)
테스트 5 〉 통과 (0.06ms, 3.64MB)
테스트 6 〉 통과 (0.60ms, 4.2MB)
테스트 7 〉 통과 (17.18ms, 4.21MB)
테스트 8 〉 통과 (41.07ms, 4.21MB)
테스트 9 〉 통과 (2664.47ms, 5.36MB)
테스트 10 〉 통과 (1422.01ms, 5.56MB)
테스트 11 〉 통과 (0.01ms, 4.16MB)
테스트 12 〉 통과 (0.01ms, 3.68MB)