Computer Science & Engineering

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

문제

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

• x에 있는 "110"을 뽑아서, 임의의 위치에 다시 삽입합니다.

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

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

풀이

    이 문제는 혼자 풀었을 때 시간초과를 해결하지 못하여 풀이를 보고 풀었다. 우선 110이 사라지고 난 다음 생기는 110도 처리를 해주어야된다는 것을 뒤늦게 알았다. 풀이를 보고 stack을 이용하면 쉽게 풀린다는 것을 알았다. 또 110을 삽입하는 위치가 오른쪽에서 시작하여 연속되는 1의 앞부분에 붙여 넣으면 된다는 것을 문제만 보고 떠올리기 쉽지 않았다. 이 부분만 알고 풀면 굉장히 쉽게 풀 수 있는 문제이다. 코드의 순서는 다음과 같다.

1. 지워진 문자열의 문자를 하나씩 stack에 넣으며 110을 찾으면 지우고 카운트(110의 개수)를 센다.
2. 110이 모두 지워진 문자열에서 뒤에서부터 1이 아닌 숫자가 나올 때까지 탐색한다. 즉 예를들어 001001111이 있을 경우 110들은 00100____1111 위치에 들어가야지 최소 숫자가 나오게 된다.
3. 위치를 찾은 경우 삽입하려는 위치 앞부분의 문자열을 정답 문자열에 붙여넣는다.
4. 110의 개수만큼 정답 문자열에 붙여넣는다.
5. 삽임하려는 위치 뒷부분 문자열을 정답 문자열에 붙여넣는다.

코드

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

using namespace std;

vector<string> solution(vector<string> s) {
    vector<string> answer;
    vector<char> st; //110을 지우고 남은 문자열
    int cnt = 0; //지워진 110의 개수
    for(string str : s) {
        cnt = 0;
        st.clear();
        for(int i = 0; i < str.size(); i++) { //110을 모두 지우기
            if(str[i] == '1') st.push_back('1'); //만약 0이 아니면 스택에 넣음
            else {
                if(st.size() >= 2 && st[st.size()-1] == '1' && st[st.size()-2] == '1') { //110을 찾으면 110개수를 늘리고 스택에서 지우기
                    cnt++;
                    st.pop_back();
                    st.pop_back();
                }
                else
                    st.push_back('0');
            }
        }
        int i;
        for(i = st.size()-1; i >= 0; i--) { //뒤에서 시작하여 연속된 1의 앞부분에 110붙이기
            if(st[i] == '1') continue;
            else break;
        }
        
        string ret = ""; 
        
        for(int k = 0; k <= i; k++) //연속된 1 앞부분 붙여넣기
            ret += st[k];
        
        for(int c = 0; c < cnt; c++) //110 붙여넣기
            ret += "110";
        
        for(int k = i+1; k < st.size(); k++) //연속된 1 뒷부분 붙여넣기
            ret += st[k];
        
        answer.push_back(ret);
    }
    
    return answer;
}

결과

풀이 방법만 알면 절대 어렵지 않은 문제였지만 이런 풀이과정을 생각해낸다는 것이 굉장히 어렵다. stack을 잘 다룬다고 생각하였지만 이렇게 실전에 적용하는 생각은 잘 하지 못하였다. 스택, 큐, 힙 등을 실제에 사용하는 문제를 많이 풀어봐야할 것 같다.