[BOJ 24979] COW Operations

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

24979번: COW Operations

 

- 문제 요약

 

첫 번째 줄에는 문자열 S가 입력됩니다.

두 번째 줄에는 정수 Q가 주어집니다. (1<=Q<=2*10^5)

세 번째 줄부터 Q개의 줄에는 정수 l과 r이 주어집니다. (1<=l<=r<=|s|)

 

베시는 'C', 'O', 'W' 세 문자만을 포함하는 최대 2*10^5의 길이의 문자열을 찾는다. 그녀는 다음 연산을 사용하여 이 문자열을 단일 'C'(그녀가 가장 좋아하는 문자)로 바꿀 수 있는지 알고 싶어 한다:

1. 두 개의 인접한 동일한 문자를 선택하고 삭제합니다.
2. 한 글자를 선택한 후 다른 두 글자로 두 글자를 순서대로 바꿉니다.

문자열 자체에서 답을 찾는 것은 베시에게 충분하지 않기 때문에,

그녀는 s의 Q(1<=Q<=2*10^5) 하위 문자열에 대한 답을 알고 싶어 한다.

길이 Q의 문자열로, i번째 하위 문자열을 줄일 수 있으면 'Y'이고, 그렇지 않으면 'N'을 출력합니다.

 

 

- 알고리즘 정리

 

C, O, W를 사용하는 하위 문자열에서 O+W가 짝수 패리티를 가지고 있고, C+O가 홀수 패리티를 가지고 있는 경우에 Y를 출력해야 합니다.

만약 O+W의 개수를 ow라고 할 때, ow가 홀수라면 ow의 값을 0으로 만들 수 없으므로 무조건적으로 N을 출력합니다.
C+O나 C+W의 개수가 짝수인 경우에도 이를 C로 줄일 수 없으므로 무조건 N을 출력합니다.

위와 같은 조건을 기억해 주면서 순회를 돌려주면 됩니다.

C, O, W의 위치보단 수가 더 중요하므로 2차원 벡터에 C, O, W의 개수를 각 인덱스에 넣어서 체크해 주고, 위의 조건에 따라 Y와 N을 출력해 주면 됩니다.

 

 

- 코드 작성

 

#include<bits/stdc++.h>
using namespace std;

string s,result;
int q;
vector<array<int,3>>v{{}};

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	cin>>s>>q;
	for(char c:s){
		v.push_back(v.back());
		if(c=='C'){
			v.back()[0]++;
		}
		if(c=='O'){
			v.back()[1]++;
		}
		if(c=='W'){
			v.back()[2]++;
		}
	}
	while(q--){
		int l,r;
		cin>>l>>r;
		array<int,3>co;
		for(int i=0;i<3;i++){
			co[i]=v[r][i]-v[l-1][i];
		}
		result+=((co[1]+co[2])%2==0&&(co[0]+co[1])%2==1)?'Y':'N';
	}
	cout<<result<<'\n';
}

코드 제출 결과