백준 1013 Contact c++

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

1013번: Contact

문제 이해하다가 탈모 올 뻔했다.

먼저 0이 연속으로 붙어서 올 경우는 첫 번째 100+1+ 뿐이다.

따라서

1. 0 연속인 부분 ex) 1100011 => 1 XXXXXX로 지워준다.

    만약 1001처럼 마지막에 1이 한 개이면 x로 바꿔준다. 10010001 이런 경우에 에러 처리 해야 하기 때문

2. 나머지 남은 부분 01 지워준다.

3. 전체 string 순회하면서 1이나 0 남아있으면 에러처리

 

// Contact

#include <string>
#include <vector>
#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;


string solution(string input) {
	if (input[input.size() - 1] == '0') // 0으로 끝나는거 말이안됨
		return "NO";
	if (input[0] == '0' && input[1] == '0')
		return "NO";

// 1XXX
	for (int i = 0; i + 1 < input.size(); i++) {
		if (i != 0 && input[i] == '0' && input[i + 1] == '0') { // 0연속 찾았다!
			int j = 0;
			while (i + j + 1 < input.size() && input[i + j + 1] == '0') // 0 연속인 개수 찾음
				j++;
			while (i + j + 1 < input.size() && input[i + j + 1] == '1') // 1 연속인 개수 찾음
				j++;
			if (input[i + j] != '1') // 0011으로 끝나는 문자열
				return "NO";
			if (input[i - 1] == 'x')
				return "NO";
			if (input[i + j - 1] == '0') { // 끝에 붙는 1 하나짜리
				input[i - 1] = 'x';
				for (int k = 0; k <= j; k++)
					input[i + k] = 'x';
			} else { // 끝에 붙는 1 두개짜리
				input[i - 1] = 'X';
				for (int k = 0; k <= j; k++)
					input[i + k] = 'X';
			}
		}
	}
	// cout << input << endl;
	for (int i = 0; i + 1 < input.size(); i++) {
		if (input[i] == '0' && input[i + 1] == '1') {
			input[i] = 'X';
			input[i + 1] = 'X';
		}
	}
	// cout << input << endl;
	for (int i = 0; i < input.size(); i++)
		if (input[i] != 'X' && input[i] != 'x')
			return "NO";
	return "YES";
}
// (100+1+ | 01)+
int main() {
	ios_base::sync_with_stdio(0);cin.tie(0);

	int n;
	cin >> n;
	string input;
	for (int i = 0; i < n; i++) {
		cin >> input;
		cout << solution(input) << '\n';
	}
}

https://ko.wikipedia.org/wiki/%EA%B2%B0%EC%A0%95%EC%A0%81_%EC%9C%A0%ED%95%9C_%EC%83%81%ED%83%9C_%EA%B8%B0%EA%B3%84

결정적 유한 상태 기계 - 위키백과, 우리 모두의 백과사전

뭔 DFA라는 처음 들어보는 알고리즘으로 푸는 문제였다. 그게 뭔데;;
30분 동안 고민 해보고 안되면 해답 보려 했는데 다행히 맞는 방식으로 접근해서 풀었다.