[백준/C++] 26122 가장 긴 막대 자석

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

 

 

코드

#include <iostream>
using namespace std;

int k, l = 1, r = 0, result = 0;
char s[300001], st;
bool flag;

int main()
{
	cin >> k >> s;

	l = 1;
	st = s[0];
	flag = false;
	for (int i = 1; i < k; i++)
	{
		if (st == s[i])
		{
			if (!flag) l++;
			else r++;
		}
		else {
			st = s[i];
			flag = !flag;
			if (r == 0) r = 1;
			else
			{
				result = max(result, min(l, r) * 2);
				l = r;
				r = 1;
				flag = !flag;
			}
		}
	}
	result = max(result, min(l, r) * 2);
	cout << result;
	return 0;
}

설명

먼저 문자열을 구성하는 문자가 N, S 두 개밖에 없고 가운데를 기준으로 잘랐을 때 양쪽이 하나의 알파벳으로만 구성되어 있어야 하기 때문에 이를 잘 이용하면 된다.

 

일단 시작 부분의 알파벳을 st에 저장하고, for문은 이 다음부터 진행해나간다. 이때 flag가 false이면 왼쪽만 있는 상태, true이면 왼쪽 구성이 끝났고 오른쪽을 현재 확인하고 있다는 뜻으로 사용했다.

 

st가 s[i]가 동일할 때 flag 값에 따라 왼쪽, 오른쪽 값을 구분해서 길이를 늘려준다. st가 s[i]가 동일하지 않을 때는 두 가지 경우가 있다. (먼저 알파벳이 변경되었으니 이를 st에 대입해주고, flag를 변경한다.)  if문은 오른쪽이 존재하지 않는 경우. 즉 처음으로 다른 알파벳을 만났을 때에 해당하는데, 이때에는 r을 1로 변경해주기만 한다. 그렇지 않은 경우에는 왼쪽과 오른쪽이 모두 존재하는 경우로 기존의 오른쪽이 왼쪽이 되는 상태이다. 여기에서 가장 긴 막대자석의 길이를 구해주고,  l = r 을 해서 기존의 오른쪽에 있던 길이를 왼쪽 길이로 만들어준다. r은 1이 되고, 이제 다시 오른쪽 길이를 구해야 하니 다시 flag를 변경해준다.

 

이와 같은 방식으로 길이 계산을 마무리하고 결과를 출력한다.

느낀 점

solved.ac 랜덤 마라톤에서 만난 문제다. 실버 5 정도로 그렇게 어렵지 않는 문제라서 아이디어 자체는 금방 파악했다. 다만, 처음에 flag를 쓰지 않으려고 했는데, 그러다보니 약간 코드가 길어져서 그냥 flag를 써서 구현했다.