<스택> 백준 3986번 좋은 단어

  

 작성한 코드

#include <stack>
#include <iostream>
#include <string>

using namespace std;

int main()
{
	stack<char>gWords;
	
	int N;
	cin >> N;

	int count{};

	while (N--)
	{
		string input;
		cin >> input;
		 //입력받은 문자열 스택에 넣기
		for (auto c : input)
		{
			gWords.push(c);  // ABBAB  입력  
 		}
		// 스택이 빌때까지 반복
		while(!gWords.empty())
		{                                   //ABABB   //ABBAB             /// AAA
			char tmp = gWords.top();                  //B                 //tmp : A
			if(gWords.size() > 1)
			{
				gWords.pop();						                      // AA
			}
	        if (gWords.top() == tmp)          // A,B   // B,B             // A == A
			{
				gWords.pop();					//오류가 나는곳            //A
				count++;
			}
			else                 
			{
				tmp = gWords.top();
				gWords.pop();
			}
		}
	}
	cout << count;
}
//스택은 뒤부터나옴 
//ABAB 는 B,A,B,A  Top으로 나올 쌍이 없음 // AAA 는 A,A,A  Top이 쌍으로 나오는데 쌍이부족함
//AABB 는 B,B,A,A  Top이  쌍으로나옴  
//ABBA 는 A,B,B,A  Top을 저장하고 다음 Top이 쌍으로나옴 
//문제 AAA일때만 안됨  스택이 비어있을때 pop()을해서 오류가 떴다

 

문제원인

 

 gWords.pop()을 한 후에도 스택이 비어있지 않다고 가정하고 top()을 호출하는 부분이 있다.
if (gWords.top() == tmp) 문에서 스택이 비어있는지 확인하지 않고 top()을 호출하여 런타임 오류(stack underflow) 가 발생 가능하다.

AAA처럼 같은 문자가 홀수개로 나오면 스택이 비어있는 상태에서 pop()을 하게된다. 

 

 단어에서 같은 글자(A 또는 B)끼리 짝을 지을 수 있는지 확인해야 한다.

같은 문자가 연속으로 나오는 경우 쌍을 이루고 제거 가능하다.
최종적으로 스택이 비어 있으면 '좋은 단어'이다.

 

수정코드

 

#include <stack>
#include <iostream>
#include <string>


using namespace std;

//스택은 뒤부터나옴 
//ABAB 는 B,A,B,A  Top으로 나올 쌍이 없음 // AAA 는 A,A,A  Top이 쌍으로 나오는데 쌍이부족함
//AABB 는 B,B,A,A  Top이  쌍으로나옴  
//ABBA 는 A,B,B,A  Top을 저장하고 다음 Top이 쌍으로나옴 
int main()
{
	int N;
	cin >> N;

	int count{};

	while (N--)
	{
		string input;
		cin >> input;
		stack<char>gWords;  //반복할때마다 새로운 스택
		 //입력받은 문자열 스택에 넣기
		for (auto c : input)
		{
			if (!gWords.empty() && (gWords.top() == c))
			{
				gWords.pop();
			}
			else
			{
				gWords.push(c);
			}
 		}
		if (gWords.empty())
		{
			count++;
		}
	}
	cout << count;
}

 

스택을 while문 내부에 선언하면서 반복이 줄어들고 pop하기전에 스택이 비었는지 검사하도록 수정했다.