110 옮기기

---

📌 문제 설명

0과 1로 이루어진 어떤 문자열 x에 대해서, 당신은 다음과 같은 행동을 통해 x를 최대한 사전 순으로 앞에 오도록 만들고자 합니다.

x에 있는 "110"을 뽑아서, 임의의 위치에 다시 삽입합니다.
예를 들어, x = "11100" 일 때, 여기서 중앙에 있는 "110"을 뽑으면 x = "10" 이 됩니다. 뽑았던 "110"을 x의 맨 앞에 다시 삽입하면 x = "11010" 이 됩니다.

변형시킬 문자열 x가 여러 개 들어있는 문자열 배열 s가 주어졌을 때, 각 문자열에 대해서 위의 행동으로 변형해서 만들 수 있는 문자열 중 사전 순으로 가장 앞에 오는 문자열을 배열에 담아 return 하도록 solution 함수를 완성해주세요.

📌 제한 사항

• 1 ≤ s의 길이 ≤ 1,000,000
• 1 ≤ s의 각 원소 길이 ≤ 1,000,000
• 1 ≤ s의 모든 원소의 길이의 합 ≤ 1,000,000

📌 입출력 예

s	result
["1110","100111100","0111111010"]	["1101","100110110","0110110111"]

 

🔗 문제 링크

https://school.programmers.co.kr/learn/courses/30/lessons/77886?language=cpp

프로그래머스

---

💡 풀이 아이디어

• "110"을 모두 제거한 문자열 만들기
• "110"을 제거한 횟수 세기
• 가장 사전순으로 빠른 위치에 삽입
  • 가장 마지막 0 뒤에 삽입

📝 최종 풀이

• stack을 이용해 문자열의 "110"을 모두 제거한 문자열을 만듭니다.
• "110"을 제거한 만큼 다시 삽입하기 위한 문자열을 미리 만듭니다.
• 가장 마지막 0의 index를 찾아 뒤에 삽입합니다.
  • 문자열 중 0이 없다면 맨 앞에 제거한 문자열을 삽입합니다.

---

👩‍💻 코드

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

using namespace std;

vector<string> solution(vector<string> s) {
    vector<string> answer;
    
    for (auto& x : s) {
        stack<char> st;
        string res;
        int count = 0;

        for (char c : x) {
            st.push(c);
            if (st.size() >= 3) {
                char third = st.top(); 
                st.pop();
                
                char second = st.top();
                st.pop();
                
                char first = st.top();
                st.pop();

                if (first == '1' && second == '1' && third == '0') {
                    count++;
                } else {
                    st.push(first);
                    st.push(second);
                    st.push(third);
                }
            }
        }

        while (!st.empty()) {
            res = st.top() + res;
            st.pop();
        }

        int pos = res.find_last_of('0');
        string result;
        result.reserve(res.size() + count * 3);
        
        string insert(count * 3, '\0');
        for (int i = 0; i < count; ++i) {
            insert[i * 3 + 0] = '1';
            insert[i * 3 + 1] = '1';
            insert[i * 3 + 2] = '0';
        }
        
        if (pos == string::npos) {
            result = insert + res;
        } else {
            result = res.substr(0, pos + 1) + insert + res.substr(pos + 1);
        }

        answer.push_back(result);
    }
    
    return answer;
}