(C++) BOJ/백준 3986 - 좋은 단어

문제 출처 : BOJ 3986 - 좋은 단어 www.acmicpc.net/problem/3986

 

 

동아리에서 C++의 STL Container를 배웠다. 그중 stack에 대한 예제를 알려주셔서 풀어봤다.

단어가 주어졌을 때 같은 글자끼리 짝이 맞춰질 때, 그 단어를 좋은 단어라고 하고, 이 문제는 좋은 단어의 개수를 세는 문제이다.

 

최종 코드

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

int main() {
	int n, cnt = 0;
	cin >> n;
	while (n--) {
		stack<char> s;
		string str;
		cin >> str;
		int len = str.length();
		for (int i = 0; i < len; i++) {
			if (s.size()) {
				if (s.top() == str[i]) s.pop();
				else s.push(str[i]);
			}
			else s.push(str[i]);
		}
		if (!s.size()) cnt++;
	}
	cout << cnt << '\n';
	return 0;
}

string형 문자열 str에 문자를 입력 받은 후, 문자열의 길이만큼 반복되는 for문을 만들었다.

 

for문 내에서는 stack에 저장된 원소들의 개수를 반환하는 size() 메서드를 이용해 조건문을 만들었다.

 

조건문 내에서는 stack에 원소를 저장할 수 있는 push() 메소드와,

stack에 가장 마지막으로 들어온 원소를 삭제하는 pop() 메소드를 사용했다.

 

stack에 1개 이상의 원소가 있으면,

가장 마지막 원소와 현재 인덱스의 원소를 비교한 후에

같으면 pop()을, 같지 않으면 push()를 해주었다.

 

stack에 원소가 1개도 없으면 push()를 통해 현재 인덱스의 원소를 저장한다.

 

for문이 종료되고 남아 있는 원소가 없으면 좋은 단어의 개수를 세는 cnt를 1 증가시켜준다.

 

while문이 n만큼 반복되고 종료되면, 마지막으로 cnt를 출력한다.

 

C++를 배우기 전에는 C로 stack 구조체와 메소드를 일일이 다 만들어서 문제를 풀었는데,

C++에서는 이렇게 다 만들어져 있으니까 아주 편했다.