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

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

코딩테스트 연습 - 큰 수 만들기

stack을 사용하여 풀 수 있는 문제입니다.

 

문제 접근법

• stack에 number의 원소 하나를 넣습니다.
• 다음 원소가 들어가기 전에 stack에 있는 원소가 다음 원소보다 작을 경우 해당 원소를 stack에서 제거하고 k를 1감소시킵니다.
  • 제거가 됬을 경우 다시 stack안에 있는 원소와 다음 원소를 확인합니다.
    • stack에 있는 원소가 다음 원소보다 작다면 이번에도 stack에서 원소를 제거 후 k를 1감소시킵니다.
• 위 작업을 k가 0이 될 때 까지 반복합니다.
• stack에 남아있는 값들을 string 배열에 더해주고 reverse 해줍니다.

아래는 코드입니다.

#include <string>
#include <vector>
#include <stack>
#include <algorithm>
 
using namespace std;
 
string solution(string number, int k) {
    string answer = "";
    int nLen = number.size();
    int len = nLen - k;
    stack<char> s;
    
    for(int i = 0; i < nLen; i++)
    {
        char c = number[i];
        
        while(!s.empty() && k > 0)
        {
            char temp = s.top();
            
            if(temp < c)
            {
                s.pop();
                k--;
            }
            else
                break;
        } 
        s.push(c);
    }
    
    while(s.size() != len)
        s.pop();
  
    while(!s.empty())
    {
        answer += s.top();
        s.pop();
    }
    
    reverse(answer.begin(), answer.end()); 
    
    return answer;
}