[백준] 1013번 Contact

www.acmicpc.net/problem/1013

1013번: Contact

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

int main() {
	cin.tie(NULL);
	ios::sync_with_stdio(false);
	int n;
	string s;
	cin >> n;
	for (int t = 0; t < n; t++) {
		cin >> s;
		vector<pair<char, int>> v;
		v.push_back(make_pair(s[0], 1));
		for (int i = 1; i < s.size(); i++) {
			if (s[i] == v[v.size() - 1].first) {
				v[v.size() - 1].second++;
			}
			else {
				v.push_back(make_pair(s[i], 1));
			}
		}
		int index = 0;
		while (index < v.size()) {
			if (v[index].first == '1') { //(100+1+) 타입일 때
				if (v[index].second == 1 && index + 1 < v.size() && v[index + 1].first == '0' && v[index + 1].second >= 2 && index + 2 < v.size() && v[index + 2].first == '1') {
					index += 3;
				}
				else {
					break;
				}
			}
			else { // (01) 타입일 때
				if (v[index].second == 1 && index + 1 < v.size() && v[index + 1].first == '1' && v[index + 1].second >= 1) {
					if (v[index + 1].second > 1) {
						v.insert(v.begin() + index + 2, make_pair(v[index + 1].first, v[index + 1].second - 1));
					}
					index += 2;
				}
				else {
					if (index - 1 >= 0 && v[index - 1].first == '1' && v[index - 1].second > 1) {
						v.insert(v.begin() + index, make_pair('1', 1));
					}
					else {
						break;
					}
				}
			}
		}
		cout << (index == v.size() ? "YES\n" : "NO\n");
	}
	return 0;
}

문자열이 들어오면 일단 이것을 가지고 pair<char, int> 타입의 벡터 v를 만들어주었다.

코드에서 벡터 v를 만들어주는 부분이

v.push_back(make_pair(s[0], 1));
for (int i = 1; i < s.size(); i++) {
	if (s[i] == v[v.size() - 1].first) {
		v[v.size() - 1].second++;
	}
	else {
		v.push_back(make_pair(s[i], 1));
	}
}

이 부분이다.

pair의 첫 번째 원소에는 s[i]를, 두 번째 원소에는 s[i]가 연속으로 몇 개 나오는지 그 개수를 저장하도록 했다.

예를 들어 10011001이라는 문자열이 들어온다면 벡터 v는 다음과 같이 만들어진다.

index = 0부터 시작해서 벡터를 체크한다.

v[0].first가 '1'이면 (100+1+) 타입이고 v[0].first가 '0'이면 (01) 타입이다.

이것을 체크하는 부분이

if (v[index].first == '1') {
	...
}
else {
	...
}

이 부분이다.

여기에서 v[0].first는 '1'이므로 (100+1+) 타입이다.

(100+1+) 타입은 1이 1개 나오고 0이 2개 이상 나와야 하고 그 다음에는 1이 1개 이상 나와야 한다.

즉, v[0].second는 1이어야 하고 v[1].first는 '0', v[1].second는 2 이상이어야 한다. 그리고 v[2].first는 '1'이어야 한다. 

이 조건을 표현한 것이

if (v[index].second == 1 && index + 1 < v.size() && v[index + 1].first == '0' && v[index + 1].second >= 2 && index + 2 < v.size() && v[index + 2].first == '1')

이 부분이다.

이 조건들을 만족시키므로 index를 3 증가시킨다. 그러면 index는 3이 된다.

(그런데 문제가 있다. 10011 /001 이렇게 끊긴 것이다. 1001/1001 이렇게 끊겨야 하는데 말이다.)

그래도 일단 index가 3이 되었으니 v[3]부터 다시 체크한다.

v[3].first가 '0'이므로 (01) 타입이다.

(01) 타입은 0이 1개 나오고 1이 1개 나와야 한다.

따라서 v[3].second는 1이어야 하고 v[4].first는 '1', v[4].second는 1이어야 한다.

이것을 체크하는 부분이

if (v[index].second == 1 && index + 1 < v.size() && v[index + 1].first == '1' && v[index + 1].second >= 1)

이 부분이다. (v[index + 1].second == 1이 아니라 v[index + 1].second >= 1인 이유는 뒤에서 설명합니다!)

그런데 v[3].second는 2이므로 v[index].second == 1이라는 조건에 맞지 않는다.

아무튼 (01) 타입의 조건을 충족시키지 못하므로 if문에 걸리지 못하고 else문에 걸리게 된다.

그러면 10011001은 NO인가?? 아니다. YES를 출력해야 한다.

1001/1001/ 이렇게 끊어져야 하는데 10011/001 이렇게 잘못 끊어져서 이런 문제가 발생했다. 따라서 else문 안에서 처리해주어야 한다.

하나 앞에서 '1'이 2개 이상이라면 앞에서 '1' 한개를 빌려오면 된다.

(100+1+) 타입에서는 마지막에는 1이 한 개 오든 두 개 오든 100개가 오든 상관없이 조건을 충족하기 때문이다.

따라서 else문 안에서 v[index - 1].first가 '1'이고 v[index - 1].second가 1보다 큰지를 체크해준다. 

if (index - 1 >= 0 && v[index - 1].first == '1' && v[index - 1].second > 1)

v[2].first는 '1'이고 v[2].second는 2이므로 이 if문에 걸리게 된다.

이 if문 안에서는 

v.insert(v.begin() + index, make_pair('1', 1));

벡터 v에 ('1', 1)을 끼워넣는 것이다.

즉 벡터 v는 다음과 같이 된다.

앞에서 '1' 하나를 빌려왔으므로 사실 v[2]는 ('1', 1)로 바뀌어야 하는데 이미 지나온 index이므로 그냥 둬도 상관없다.

아무튼 index는 그대로 3이다.

여기에서 v[3].first는 '1'이므로 (100+1+) 타입이다.

(100+1+) 타입은 1이 1개 나오고 0이 2개 이상 나와야 하고 그 다음에는 1이 1개 이상 나와야 한다.

즉, v[3].second는 1이어야 하고 v[4].first는 '0', v[4].second는 2 이상이어야 한다. 그리고 v[5].first는 '1'이어야 한다. 

이 조건을 모두 만족시키므로 index를 3 증가시킨다. 그러면 index는 6이 된다.

벡터의 크기는 6이므로 

while (index < v.size())

이 조건에 맞지 않으므로 index가 6인채로 while문을 빠져나오게 된다.

v.size()인 6과 index인 6이 일치하므로 YES를 출력한다.

v.size()와 index가 일치하지 않는다는 것은 정상적으로 while문을 빠져나온 것이 아니라 조건에 맞지 않아 break로 빠져나온 것이기 때문에 NO를 출력한다.

 

또 다른 예로 01100011이 입력으로 들어왔다고 하자.

이것은 01/100011으로 조건을 충족하므로 YES를 출력해야 한다.

벡터 v는 다음과 같다.

index는 0부터 시작한다.

v[0].first가 '0'이므로 (01) 타입이다.

(01) 타입은 0이 1개 나오고 1이 1개 나와야 한다.

따라서 v[0].second는 1이어야 하고 v[1].first는 '1', v[1].second는 1이어야 한다.

그런데 v[1].second는 2이다.

(01) 타입의 조건이 맞는지 체크하는 부분인

if (v[index].second == 1 && index + 1 < v.size() && v[index + 1].first == '1' && v[index + 1].second >= 1)

이 부분에서 v[index + 1].second == 1이 아니라 v[index + 1].second >= 1인 이유가 바로 이것이다.

v[index + 1].second > 1이면 '1'을 하나만 쓰고 나머지는 뒤로 넘기는 것이다.

사실 '1'을 하나만 가져오고 나머지 '1'들은 뒤로 넘기는 것이므로 ('1', 1)이 추가되고 v[1].second는 1로 바뀌어야 하는데 이미 지난 index이므로 그대로 둬도 상관없다.

이렇게 하고 index를 2 증가시킨다.

이제 index는 2이다.

여기에서 v[2].first는 '1'이므로 (100+1+) 타입이다.

(100+1+) 타입은 1이 1개 나오고 0이 2개 이상 나와야 하고 그 다음에는 1이 1개 이상 나와야 한다.

즉, v[2].second는 1이어야 하고 v[3].first는 '0', v[3].second는 2 이상이어야 한다. 그리고 v[4].first는 '1'이어야 한다. 

이 조건을 모두 만족시키므로 index를 3 증가시킨다. 그러면 index는 5이 된다.

index가 5가 되면 while문의 조건인 index < v.size()에 맞지 않으므로 while문을 빠져나온다.

index가 5인채로 빠져나왔고 v.size()는 5이므로 YES를 출력한다.

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

int main() {
	cin.tie(NULL);
	ios::sync_with_stdio(false);
	int n;
	string s;
	cin >> n;
	for (int t = 0; t < n; t++) {
		cin >> s;
		vector<pair<char, int>> v;
		v.push_back(make_pair(s[0], 1));
		for (int i = 1; i < s.size(); i++) {
			if (s[i] == v[v.size() - 1].first) {
				v[v.size() - 1].second++;
			}
			else {
				v.push_back(make_pair(s[i], 1));
			}
		}
		int index = 0;
		while (index < v.size()) {
			if (v[index].first == '1') { //(100+1+) 타입일 때
				if (v[index].second == 1 && index + 1 < v.size() && v[index + 1].first == '0' && v[index + 1].second >= 2 && index + 2 < v.size() && v[index + 2].first == '1') {
					index += 3;
				}
				else {
					break;
				}
			}
			else { // (01) 타입일 때
				if (v[index].second == 1 && index + 1 < v.size() && v[index + 1].first == '1' && v[index + 1].second >= 1) {
					if (v[index + 1].second > 1) {
						v.insert(v.begin() + index + 2, make_pair(v[index + 1].first, v[index + 1].second - 1));
					}
					index += 2;
				}
				else {
					if (index - 1 >= 0 && v[index - 1].first == '1' && v[index - 1].second > 1) {
						v.insert(v.begin() + index, make_pair('1', 1));
					}
					else {
						break;
					}
				}
			}
		}
		cout << (index == v.size() ? "YES\n" : "NO\n");
	}
	return 0;
}