[프로그래머스 lv3] 110 옮기기 풀이

✅ 프로그래머스의 모든 문제와 해설 보기[클릭]

 

해설

문자열 x가 주어질 때, 문자열에서 110을 뽑아내자. 

이때, 문자열을 한번만 훑는 것이 아니라, 스택을 활용하여 110을 제거하고 합쳐진 문자열에서의 110도 같이 제거한다.

 

예를 들어 문자열이 111100... 이고 스택에 네번째 원소까지 들어있다고 가정해보자.

1) 현재 스택에는 1111이 들어있고 이제 0을 스택에 넣을 차례이다. 스택에서 가장 최근 두 수를 뽑으면 모두 1인데, 11은 0과 만나 110이 되므로 이를 스택에서 제거한다.

2) 스택에는 11이 남아있게 된다. 이제 새로운 또 다른 0을 스택에 넣을 차례이다. 스택에서 가장 최근 두 수를 뽑으면 모두 1인데, 11은 0과 만나 110이 되므로 이를 스택에서 제거한다.

3) 결국 스택에는 아무것도 남지 않는다.

 

문자열의 각 자리수를 스택에 넣되 스택에서 가장 최근의 두 원소가 모두 1이고 새롭게 넣을 원소가 0이면 이를 모두 스택에서 제거하는 것이다. 이렇게 하면 스택에는 연속된 110을 제거한 결과만 남게 된다.

 

연속된 110을 모두 제거한 문자열을 left라고 할 때, 그동한 제거한 110을 모두 붙인 결과를 left에 넣어주어야 한다.

결과 문자열을 사전 순으로 가장 앞에 오게 하려면  left의 가장 오른쪽 문자로 부터 연속된 1이 시작되는 지점에 110더미를 붙이면 된다.

 

위의 과정으로 구한 새로운 문자열을 모두 벡터에 저장해 리턴하면 정답이다.

 

 

코드

#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <tuple>
#include <vector>
#include <stack>
#include <queue>
#include <deque>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <iostream>

using namespace std;
using ii = pair<int, int>;
using iii = tuple<int, int, int>;

#define X first
#define Y second

vector<string> solution(vector<string> s) {
    
    vector<string> ans;
    
    for (auto x : s) {
        
        int cnt = 0;
        stack<char> st;
        
        //"110"을 모두 뺀 문자열(left) 구하기
        for (auto c : x) {
            if ((int)st.size() < 2) {
                st.push(c);
                continue;
            }
            
            char t1 = st.top();
            st.pop();
            char t2 = st.top();
            st.pop();
            
            if (t1 == '1' && t2 == '1' && c == '0') {
                cnt++;
                continue;
            }
            
            st.push(t2);
            st.push(t1);
            st.push(c);
        }
        
        string left = "";
        while (!st.empty()) {
            left = st.top() + left;
            st.pop();
        }
        
        //뺀 만큼 붙여넣어야 하는 "110"
        string sub = "";
        for (int i=0; i<cnt; i++) sub += "110";
        
        //left의 오른쪽 끝에서 부터 '1'의 연속이 끝나는 지점에 연속된 "110"(sub) 붙이기
        int i = (int)left.size()-1;
        while (left[i] == '1') i--;
        
        string r = left.substr(0, i+1) + sub + left.substr(i+1);
        ans.push_back(r);
    }
    
    return ans;
}