[ 백준 BOJ ] 1013번 - Contact (C++)

https://www.acmicpc.net/problem/1013

 

 

생각 흐름

• 뒤에서부터 하나씩 체크하기로 결정
• 1이 나오지 않은 상태에서 0이 나오면 무조건 NO인 결과를 내뱉어야 하는 것을 알았다.
• 또한, s[0]이 0일 때는 마지막 1의 위치가 1이 아니면 NO를 내뱉어야 하고, s[0]이 1일 때는 마지막 1의 위치가 -1이 아니면 즉, s[0]이 1인데 1001와 같이 끝난 게 아니면 NO를 내뱉어야 한다.
• 제출했더니 실패, 101와 같이 1과 1사이에 2개의 0개 와야되는 것을 확인
• 이에 대해 마지막 1의 위치가 -1이 아니고 이 때 중간에 0의 값이 있을 때, 0의 개수를 세줘서 2개 미만이면 NO를 내뱉게 했다.

 

#include <iostream>
#include <vector>
#include <map>
#include <queue>
#include <memory.h>
#include <set>
#include <algorithm>
#include <cmath>
#include <unordered_map>

#define endl '\n'

using namespace std;

int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    int T;
    cin>>T;
    
    for(int i = 0; i<T; i++){
        string s;
        cin>>s;
        
        int lastOne = -1;
        bool inZero = false;
        bool comp = true;
        for(int j = (int)s.size()-1; j>=0; j--){
            if(lastOne==-1 && s[j]!='1'){
                comp = false;
                break;
            }else if(lastOne==-1 && s[j]=='1'){
                lastOne=j;
            }else if(lastOne!=-1 && s[j]!='1'){
                inZero = true;
                continue;
            }else{
                if(inZero){
                    int zeroCount = 0;
                    for(int h = j; h<=lastOne; h++){
                        if(s[h]=='0') zeroCount++;
                    }
                    if(zeroCount <= 1 && lastOne-j==2){
                        lastOne = j;
                    }else if(zeroCount <= 1 && lastOne-j!=2){
                        comp=false;
                        break;
                    }else if(zeroCount > 1 && lastOne-j==2){
                        comp=false;
                        break;
                    }else{
                        lastOne = -1;
                    }
                    inZero=false;
                }else{
                    continue;
                }
            }
        }
        
        if(s[0]=='0'){
            if(lastOne!=1){
                comp=false;
            }
        }else{
            if(lastOne != -1){
                comp=false;
            }
        }
        
        if(comp){
            cout<<"YES"<<endl;
        }else{
            cout<<"NO"<<endl;
        }
    }
    
    return 0;
}