Educational Codeforces Round 57 B. Substring Removal

B번) 문제 링크 : https://codeforces.com/contest/1096/problem/B

이번 코포는 자료형과 관련된 것들을 제대로 다룰줄 모르면 헤맬 수 밖에 없었다.

이 문제에 대한 설명부터 하자면 최소 2개 이상의 문자로 구성된 string이 왔을 때,

substring을 빼서 한 글자만 남아있거나 아무 것도 없게 만드는 경우의 수를 구하는 것이다.

얼핏 보면 "전체 다 따져야하나?"라는 생각이 들지만 substring이라는 것을 기억해야 한다.

substring은 부분 문자열이다. 즉, 연결되어 있는 문자열 1개를 제거한다는 뜻이다.

그럼 이제 문제를 다시 보자.

우리는 특정 1종류의 문자만 남도록 혹은 하나도 남지 않도록 만들어야 한다.

크게 3가지 경우로 나눌 수 있다.

i) 앞의 동일한 문자들만 남는 경우

ii) 뒤의 동일한 문자들만 남는 경우

iii) 아무 것도 남지 않는 경우

이 3가지만 따져준다면 쉽게 풀 수 있게 된다.

iii)의 경우의 수는 물론 1개이다. 그리고 i)과 ii)는 맨 앞의 문자가 연속해서 나타나는 개수(front_count), 맨 뒤의 문자가 연속해서 나타나는 개수(end_count)를 따져주면 된다.

따라서 경우의 수는 front_count + end_count + 1이 된다. ( 앞의 문자들만 남게 하거나 뒤의 문자들만 남게 하거나 아무 것도 남지 않게 하기 )

하지만 여기서 추가로 따져줘야 하는 경우가 있다. 바로 앞 문자와 뒤 문자가 같은 경우이다.

예를 들면 aaabbaa와 같은 경우이다. 이 경우에는 앞의 문자와 뒤의 문자가 a로 같다. 따라서 앞의 문자들만 남게 혹은 뒤의 문자들만 남게 만들지 않고 앞의 문자와 뒤의 문자가 적절히 섞여있어도 a만 남게 된다는 뜻이다.

따라서 이전에 구한 결과에 front_count * end_count를 더해줘야 한다.

+ 글의 처음 부분에서 자료형을 잘 알아야 한다고 언급한 부분이 있다. 이 문자열의 길이는 최대 2 * 10^5 이다. 즉, front_count와 end_count를 곱했을 때 최악의 경우 약 10^10까지 나올 수 있다는 뜻이다. 그렇기 때문에 결과를 받을 result를 long long의 형태로 만들어줘야 한다.

하지만, result를 long long으로 선언하고 result = front_count * end_count를 할 경우 우변의 결과가 int의 범위를 넘어가면 result는 long long이지만 dump된 값을 가지게 된다. 따라서, front_count와 end_count 역시 long long으로 선언해주거나 형변환해서 연산을 수행해야 한다.

---

- 소스코드 -

#include<iostream>
using namespace std;
char str[200001];
int main(void) {
	int n;
	cin >> n;
	cin >> str;
	long long front_count = 0;
	long long end_count = 0;
	char start = str[0];
	char end = str[n - 1];
	while (str[front_count] == start) {
		front_count++;
	}
	while (str[n - end_count-1] == end) {
		end_count++;
	}
	long long result = front_count + end_count + 1;
	if (start == end) {
		result += front_count * end_count;
	}
	cout << result%998244353;
}