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

리뷰

프로그래머스

 

어떤 숫자에서 k개의 수를 제거했을 때 얻을 수 있는 가장 큰 숫자를 구하는 문제

 

 

전역 변수

없음

 

 

함수

없음

 

 

문제풀이

1. 정수형 변수 n에 매개변수로 받은 문자열 number의 size를 저장해 준다.
2. 문자형 벡터 stack을 초기화 하고 n번의 for문을 개행해 준다.
3. stack이 비지 않았고, 스택의 맨 뒤의 문자가 현재 문자보다 작고 k가 있을경우 스택의 맨뒤 요소를 빼고 k를 감소시킨다.
4. 스택에 현재 문자를 추가해 준다. for문이 종료될 때까지 해당 작업을 반복해 준다.
5. for문이 종료되었다면 이제 k가 남아있을 경우를 처리해 주어야 한다.
6. 남은 k개 만큼 스택의 뒤에서 숫자를 제거해 준다.

 

참고 사항

테케의 마지막에 남은 k개 만큼 스택에서 요소를 제거해 줘야 하는 엣지케이스가 숨어있다.

 

 

정답 코드

#include <bits/stdc++.h>

using namespace std;

string solution(string number, int k) {
    int n = number.size();
    vector<char> stack;
    for (int i = 0; i < n; i++) {
        while (!stack.empty() && stack.back() < number[i] && k) {
            stack.pop_back();
            k--;
        }
        stack.push_back(number[i]);
    }
    while (k--) stack.pop_back();
    
    string s = "";
    for (const char& ch : stack) s += ch;
    
    return s;
}