큰 수 만들기(해결)

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

구현 아이디어 4분 구현 30분

처음에는 접근이 아예 틀렸다. 작은 수를 찾아서 없애면 되지 않을까 했지만 테스트 케이스 3번이 그 반례였다. 그래서 타이머를 멈추고 다시 풀어 봤지만 틀렸다.
도대체 어디가 틀렸을까? 질문하기에 있는 반례들을 열심히 적용해 봤지만 아직 반례가 없다. 테스트 케이스는 전부 통과하는데 채점하면 2번~10번을 전부 틀린다. 몇 시간 째 이유를 찾는 중이다. 얼른 풀고 싶다.

접근 방법

핵심: 스택을 활용할 것
1. number 문자열을 앞에서부터 돌면서 현재 number[i]의 값이 stack의 top보다 크다면 그렇지 않을 때 까지 stack을 pop 한다.
2. 1번의 과정이 끝나면 stack에 number[i]를 push 한다.
3. pop 과정이 k번 보다 작을 수 있기 때문에 stack을 차이만큼 pop 한다.
예: "99991"이 number이고 k가 3일 때, pop 과정을 한 번도 거치지 않기 때문에 k는 여전히 3일 것이다. 나는 99991에서 3개의 수를 뺀 2자리 숫자를 얻어야 한다. 그렇기 때문에 stack의 사이즈를 2가 될 때 까지 pop 한다.
4. stack에 남은 원소들을 가지고 answer를 완성한다.

#include <string>
#include <vector>
#include <stack>

using namespace std;

string solution(string number, int k) {
    string answer = "";
    stack<char> s;
    int K = k;
    
    for(int i = 0; i < number.size(); ++i)
    {
        while(!s.empty() && k != 0)
        {
            char c = s.top();
            if(c < number[i])
            {
                s.pop();
                --k;
            }
            else break;
        }
        s.push(number[i]);
    }
    
    while(s.size() > number.size() - K) s.pop();
    
    int res = 0, mul = 1;
    for(int i = 0; i < number.size() - k && !s.empty(); ++i)
    {
        res += (s.top() - '0') * mul;
        mul *= 10;
        s.pop();
    }
    
    answer = to_string(res);
    
    return answer;
}

---

개인적인 감상. 큰 수 찾기는 스택이다.

---

글을 쓰고 혹시 원소들을 숫자의 형태로 res에 담고 다시 to_string(res)를 통해 answer에 담아주기 때문에 틀렸나 싶어 그 부분을 고쳤더니 100점이 나왔다. number는 2자리 이상, 1,000,000자리 이하인 숫자입니다. 이 부분을 읽고 number가 1,000,000 이하라고 생각하다니... 문제 잘 파악하자.

풀이

#include <string>
#include <vector>
#include <stack>

using namespace std;

string solution(string number, int k) {
    string answer = "";
    stack<char> s;
    int K = k;
    
    for(int i = 0; i < number.size(); ++i)
    {
        while(!s.empty() && k != 0)
        {
            char c = s.top();
            if(c < number[i])
            {
                s.pop();
                --k;
            }
            else break;
        }
        s.push(number[i]);
    }
    
    while(s.size() > number.size() - K) s.pop();
    
    stack<char> s2;
    while(!s.empty())
    {
        s2.push(s.top());
        s.pop();
    }
    
    for(int i = 0; i < number.size() - k && !s2.empty(); ++i)
    {
        answer += s2.top();
        s2.pop();
    }
    
    return answer;
}