백준 3986번 좋은단어 (C++)(부제 맞왜틀..)

문제

정답 코드

#include <iostream>
#include <algorithm>
#include <string>
#include <stack>
using namespace std;

stack <char> a;

int check(string s)
{
	if (s.size()%2 != 0)
		return (0);
	for (auto it : s)
	{
		if (a.empty())
			a.push(it);
		else if (a.top() == it)
			a.pop();
		else
			a.push(it);
	}
	char c1,c2;
	while (!a.empty())
	{
		 c1 = a.top();
		 a.pop();
		 if (a.empty())
		 	return (0);
		c2 = a.top();
		a.pop();
		 if (c1 != c2)
		 {
			while (!a.empty())
			{
				a.pop();
			}
			return (0);
		 }
	}
	return (1);
}

int main()
{
	int n;
	ios :: sync_with_stdio(0);
	cin.tie(0);
	string s;
	cin >> n;
	int	cnt =0;
	for (int i=0;i < n; i++)
	{
		cin >> s;
		if (check(s))
			cnt++;
	}
	cout << cnt;
}

문제 풀이의 흐름

• 문자열을 입력 받는다.

• 문자를 하나씩 보면서 스택이 비어있다면 문자 하나를 넣는다

• 스택에 있는 문자와 현재 문자가 같은 지 확인한다.

• 같다면 스택을 터트리고 다르다면 스택에 푸쉬한다.

• 반복한다.

• 다 넣었다면 다시 하나씩 터트려보면서 확인한다.

주의 할 점

이 문제는 반레가 조금 있다. 스택을 사용하지 않고 함수로 풀려고 해서 필자는 맞왜틀 상황에 직면했었다.

필자가 걸린 반례는 ABBABAAB반례로 무조건 앞 뒤로 짝이 있어야 한다고 생각했던 생각의 모순이었다.

앞으로 짝 찾기 문제는 최대한 스택으로 풀도록 노력해야겠다.

반성 및 고찰

자꾸 충분한 테스트를 돌지지 않고 제출을 하는 나의 모습을 발견한다.

코딩 테스트에서도 그렇게 할 것인가? 충분히 더 생각해보고 코드를 짜야겠다.

이전에 틀렸던 코드를 공유하자면 다음과 같다.

#include <iostream>
#include <algorithm>
#include <string>

using namespace std;

int check(string s)
{
	int start = 0;
	if (s.size() % 2 != 0)
		return (0);
	int end = s.size() -1;
	while (start < end)
	{
		if (s[start] == s[end])
		{
			start++;
			end--;
		}
		else if (s[start] == s[start + 1])
		{
			start+=2;
		}
		else if (s[end] == s[end - 1])
			end-=2;
		else
			return (0);
	}
	return (1);
}

int main()
{
	int n;
	ios :: sync_with_stdio(0);
	cin.tie(0);
	string s;
	cin >> n;
	int	cnt =0;
	for (int i=0;i < n; i++)
	{
		cin >> s;
		if (check(s))
			cnt++;
	}
	cout << cnt;
}

이렇게 풀면 ABBABAAB에서 걸려서 틀린다.

부끄럽다 증말..

Uploaded by N2T