[프로그래머스] 110 옮기기 (C++)

문제 링크: https://programmers.co.kr/learn/courses/30/lessons/77886

코딩테스트 연습 - 110 옮기기

1. 주의할 점

- 브루트포스로 풀지 않는다

- 선형시간(O(N))내로 푼다

 

2. 구현

- 입력 받은 문자열에 대해 110의 개수를 확인한다

- 110을 제외한 문자열을 Deque에 담도록 한다

- 110의 개수가 1개 이상일 때, 문자열 어디에 삽입하면 사전 순서로 가장 빠를지 예상한다

Deque에는 다음과 같은 형태만 들어갈 수 있다
1. 연속된 0
2. 01 또는 10의 반복
3. ...111...
즉, '110'이 들어갈 수 없다

사전상 가장 빠른 위치
1. 가장 우측에 위치한 0을 찾는다
2. 해당 위치까지의 문자들을 순서대로 Result에 담는다
3. '110'의 개수만큼 Result에 더한다
4. 1번의 우측에 존재했던 문자들을 Result에 더한다

 

#include <string>
#include <vector>
#include <queue>
#include <iostream>
using namespace std;

vector<string> solution(vector<string> s) {
    vector<string> answer;
    for(string str: s){
        deque<char> dq;
        int cnt=0,idx=0,len = str.size();
        //110개수 세기, 제거한 값 dq에 넣기
        for(int i=0;i<len;i++){
            char c = str[i];
            dq.push_back(c);
            idx++;
            if(idx>2){
                if(dq[idx-3]=='1' && dq[idx-2]=='1' && dq[idx-1]=='0'){     //110
                    dq.pop_back();
                    dq.pop_back();
                    dq.pop_back();
                    cnt++;
                    idx-=3;
                }
            }
        }
        string result="";
        int lastZero = -1;
        for(int i=idx-1;i>=0;i--){
            if(dq[i]=='0'){
                lastZero=i;
                break;
            }
        }
        
        for(int i=0;i<=lastZero;i++)
            result+=dq[i];
        while(cnt--)
            result+="110";
        for(int i=lastZero+1;i<idx;i++)
            result+=dq[i];
        answer.push_back(result);
    }
    return answer;
}