백준 문제 2812번 크게 만들기 문제풀이 c++

https://www.acmicpc.net/problem/2812

2812번: 크게 만들기

 

문제해석

 

 

이 문제를 첨봤을때 큐 생각이 나서 큐로 풀어보려 했으나 마땅히 명쾌한 풀이가 생각이 안나오길래 알고리즘 분류를 열어보았는데 큐가아니라 스택이 있었다.

 

큐는 생각해봤으면 스택도 생각해봤을법한데 왜 그걸 생각 못해봤을까....

 

아무튼 스택을 사용한 풀이는 다음과 같다.

 

숫자를 순차적으로 넣는데 넣기전에 스택의 탑과 넣을값과 비교를해서 넣을 값이 큰 경우가 될때까지 스택의 탑에 있는 원소를 지우는것을 반복하다 넣을값이 스택의 탑의 원소보다 작을때가 되었을때 넣으면된다.

 

지울때마다 k값을 감소 시키고 모든 숫자를 스택에 넣었는데 k값이 0보다 크다면 k개만큼 스택의 탑원소를 제거해주면된다.

 

예를들어 예제 3번 10 4 4177252841을 이 방식으로 해결해보면 아래 처럼 동작한다.

 

 

 

위에서 설명한 방식을 벡터를 스택처럼 사용하여 코드를 구현하였다.

 

 

코드

 

#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
using namespace std;
vector <int> v;
int n,k;
int main(){
	cout.tie(NULL);
    cin.tie(NULL);
    ios_base::sync_with_stdio(false);
    cin>>n>>k;
    v.push_back(10);
    for(int i=0; i<n; i++)
    {
        char c;
        cin>>c;
        int x=(int)c-(int)'0';
        if(k>0)
        {
            if(v.back()>x)
            {
                v.push_back(x);
            }
            else
            {
                while(v.back()<x)
                {
                    v.pop_back();
                    k--;
                    if(k==0)
                    {
                        break;
                    }
                }
                v.push_back(x);
            }
        }
        else
        {
            v.push_back(x);
        }
    }
    for(int i=0; i<k; i++)
    {
        v.pop_back();
    }
    for(int i=1; i<v.size(); i++)
    {
        cout<<v[i];
    }
}