프로그래머스 Level 2 큰수만들기

큰수만들기 (프로그래머스 Level 2)

https://school.programmers.co.kr/learn/courses/30/lessons/42883

‘백트래킹’으로 접근하였다가,
런타임 에러가 발생하여, 뭐가 문제인가 싶었으나
재귀가 너무 깊어진 것이 문제였다

이후, 가장 ‘큰 수’가 앞에 오는 것이 정답과 관련이 있다는 점은 파악하였으나
구상이 dfs 방식에서 벗어나지 못하였고
결국 검색을 통해 코드를 확인하였다

Code

#include <string>
#include <vector>

using namespace std;

string solution(string number, int k) {
    string answer = ""; // 결과로 반환할 문자열 초기화

    for (char digit : number) 
    {
        // answer가 비어있지 않음
        // 문자열이 마지막이 현재의 문자보다 작다면, 그 문자를 제거
        // 제거할 수 있는 k가 남아있는지를 확인하기
        // 현재 문자열을 기준으로 '제거할 만큼'의 수를 파악한다
        // 첫 자릿수가 높을수록 큰 수가 완성됨
        
        while (answer.empty() == false &&
            answer.back() < digit &&
            k > 0) 
        {
            answer.pop_back();
            k--;
        }

        // 현재 숫자를 결과 문자열에 추가
        answer.push_back(digit);
    }

    // K가 남아있다면 뒤에서부터 처낸다
    answer.erase(answer.size() - k, k);

    return answer;
}

해결 아이디어

1. 반복문을 통해 모든 문자를 순회하며 answer에 push_back을 해준다
   
2. 현재 문자가 answer의 가장 마지막 문자보다 크고,
   아직 제거해야할 수가 남아있다면 해당 수를 제거하고
   지울 수를 하나 줄인다
   
3. 혹시 지울 수가 남아있는 경우, 뒤쪽에서 잘라준다