[백준 BOJ] 3986번 좋은 단어 (C++/cpp)

문제 설명

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

3986번: 좋은 단어

 

접근 방법 - 스택과 문자열을 이용한 문제

백준의 3986번 문제는 스택과 문자열의 성질을 이용해서 해결해야 하는 문제이다.

해당 문제는, 입력받은 단어들에 대하여 좋은 단어의 개수를 출력해야 하는 문제이다.

여기서 좋은 단어란, 같은 글자끼리 아치형 곡선으로 짝을 지었을 때 그 선들끼리 교차하지 않는 단어를 의미한다.

이에 대한 설명을 위해, 아래 그림도 참고해보길 바란다.

 

필자는, 위처럼 좋은 단어가 되기 위해 갖추어야 하는 조건들을 아래처럼 생각하였다.

- 글자끼리 짝을 이루어야 한다. -> A와 B의 글자 수가 둘 다 짝수여야 한다.
- 위 그림처럼, 아치형 곡선끼리 교차점이 없어야 한다. (스택 이용 -> 자세한 설명은 아래 참고)

필자는 이 조건들을 고려하면서, 아래의 순서대로 코드를 작성하여 문제를 해결하였다.

 

코드의 실행 순서

1) 단어의 개수(n)를 입력받는다.

 

2) 좋은 단어의 개수를 카운팅 할 변수 num을 0으로 초기화하여 선언한다.

 

3) n의 크기만큼, 반복문을 실행하며 아래의 연산을 취한다.

- 단어(st)를 하나 입력받고 스택을 선언한다.

- 반복문을 통해 st의 문자들을 하나씩 탐색한다.

만일 스택이 비어있거나 스택의 top 값이 현재 탐색한 문자와 일치하지 않다면 현재 문자의 값을 스택에 push한다.

다만 스택의 top 값이 현재 탐색한 문자의 값과 일치하다면 스택에 있어 pop 연산을 취한다.

- 모든 연산이 끝났다면, 스택이 비어있는지 확인한다. 만일 비어있다면, 이는 좋은 단어이기 때문에 num에 1을 더한다.

 

4) 반복문의 연산이 모두 끝났다면, 최종적으로 저장된 num 값을 출력하고 실행 종료한다.

반응형

 

성공한 코드

#define _CRT_SECURE_NO_WARNINGS
#pragma warning(disable: 4996)
#include <iostream>
#include <stack>
#include <string>
#define endl '\n'
using namespace std;

//백준 3986번 코드
int main() {
	int n;
	cin >> n;

	int num = 0;
	for (int i = 0; i < n; i++) {
		string st;
		cin >> st;

		stack<char> s;
		for (int j = 0; j < st.length(); j++) {
			if (!s.empty() && s.top()==st[j]) {
				s.pop();	continue;
			}
			s.push(st[j]);
		}

		if (s.empty()) { num++; }
	}

	cout << num << endl;
}

 

제출 결과

(2022.02.26 백준 3986번 문제 제출 결과)