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

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

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

 

 

[난이도] level3
[유형] Greedy

[풀이]

나올 수 있는 모든 110을 뽑아서 남은 문자열에서 가장 뒤에 있는 0 뒤에 모든 110을 붙혀주면 되는 문제입니다.

이게 가능한 이유는 문자열에 있는 존재하는 모든 110을 제거했다면,
1이 연속으로 2개 이상 나오는 경우는 "111111"과 같이 0이 존재하지 않는 경우밖에 없습니다.
왜냐하면 0이 붙는 순간 "110"이 되어 제거되기 때문입니다.

결국 남은 문자열은
1만 남은 경우 또는 "1001010"과 같이 1 다음에는 무조건 0이 나오는 형태 두가지 경우일 수밖에 없습니다.

1만 남은 경우에는 사전순으로 작은 문자가 되려면
110들을 문자열의 앞에다가 붙혀야 합니다. ex) "110110+11111"

1과 0이 같이 나오는 "10010100" 같은 경우에는
11이 연속으로 나오는 "110"을 무조건 맨 마지막 0 뒤에 넣어야 합니다.
앞쪽에 넣게 되면 연속된 "11"에 의해 사전순으로 뒤로 밀리게 되기 때문입니다.

위 두가지 케이스를 한번에 처리하기 위해 0을 남은 문자열 앞에 더해주었습니다.
이러면 마지막 0의 위치만 찾아서 제거한 "110"들을 넣기만 하면 됩니다.

 

#include <string>
#include <vector>
using namespace std;
string sol(string str){
    string ret,ans;
    int cnt=0;
    for(auto c : str){
        if(c=='0' && ret.size()>=2 && ret.substr(ret.size()-2,2)=="11"){            
            ret.pop_back();ret.pop_back();
            cnt++;
        } else ret.push_back(c);
    }
    ret='0'+ret;
    int idx;
    for(int i=ret.size()-1;i>=0;i--){
        if(ret[i]=='0') {
            idx=i;
            break;
        }
    }
    for(int i=0;i<=idx;i++) ans+=ret[i]; 
    while(cnt--) ans+="110";
    for(int i=idx+1;i<ret.size();i++) ans+=ret[i];
    return ans.substr(1);
}
vector<string> solution(vector<string> s) {
    vector<string> answer;
    for(auto str : s) answer.push_back(sol(str));
    return answer;
}

https://github.com/has2/Problem-Solving/blob/master/programmers/level3/110_옮기기.cpp