[1일 1알고] 110 옮기

https://school.programmers.co.kr/learn/courses/30/lessons/77886

프로그래머스

 

오늘도 간단한? 문제입니다. (한번 틀림)

 

110을 뽑아내고 이를 올바른 위치에 삽입하는 문제입니다.

 

읽자마자 stack을 사용해야하는 것을 알 수 있습니다.

 

110자체는 stack방식을 통해 추출하면 될 일이고, 이후 이 110들을 어디에 삽입할지를 결정해야합니다.

 

사전 순으로 110이 들어가는 위치는 마지막으로 0이 들어간 위치가 됩니다.

왜냐하면 1110과 같은 문자열이 남아있을 수 없기 때문입니다.

---

#include <string>
#include <vector>

using namespace std;

vector<string> solution(vector<string> s) {
    vector<string> answer;


    for (string& word : s)
    {
        vector<char> stack;
        int cnt_1 = 0;
        int cnt_110 = 0;
        for (char ch : word)
        {
            if (ch == '1')
            {
                stack.push_back('1');
                ++cnt_1;
            }
            else
            {
                if (cnt_1 >= 2)
                {
                    cnt_1 -= 2;
                    ++cnt_110;
                    stack.pop_back();
                    stack.pop_back();
                }
                else
                {
                    cnt_1 = 0;
                    stack.push_back('0');
                }
            }
        }
        int N = stack.size();
        int idx_0 = -1;
        for (int i = N - 1; i >= 0; --i)
        {
            if (stack[i] == '0')
            {
                idx_0 = i;
                break;
            }
        }
        string ans;

        if (idx_0 == -1)
        {
            for (int i = 0; i < cnt_110; ++i)
            {
                ans += "110";
            }
            for (int i = 0; i < N; ++i)
            {
                ans += stack[i];
            }
        }
        else
        {
            for (int i = 0; i < N; ++i)
            {
                ans += stack[i];
                if (i == idx_0)
                {
                    for (int i = 0; i < cnt_110; ++i)
                    {
                        ans += "110";
                    }
                }
            }
        }
        
        answer.push_back(ans);
    }

    return answer;
}

 결론적으로 코드는 위와 같은 형태가 됩니다.