[백준 BOJ] 4949번 균형잡힌 세상 (C++/cpp)

문제 설명

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

4949번: 균형잡힌 세상

 

접근 방법 - 스택을 이용한 문자 연산 문제

백준의 4949번 문제는 스택을 이용하여 문자에 대한 연산을 처리해야 하는 문제이다.

해당 문제는, 특정 문자열에 대하여 소괄호 및 대괄호의 짝이 맞는지에 대한 여부를 출력해야 하는 문제이다.

필자의 경우엔 스택을 사용하여 각 괄호의 짝이 맞는지를 파악하도록 하였다.

스택에 대한 활용도가 어느 정도 있다면 해당 문제를 해결하는 데에는 크게 어려움이 없었을 거라 예상된다.

스택에 대한 활용이 아직 어색하다면, 아래의 설명과 코드를 한번 참고해보길 바란다.

필자는 아래의 순서대로 코드를 작성하여 문제를 해결하였다.

 

코드의 실행 순서

- 무한 반복문을 통하여 아래의 연산들을 수행하도록 한다.

 

1) 공백을 포함하여 문자열(ch)을 입력받는다.

(getline() 문장을 이용하여 공백을 포함한 문자열을 입력받도록 한다.)

(만일 .(점) 하나만 입력받은 경우엔 무한 반복문을 탈출하도록 한다.)

 

2) 문자에 대한 연산을 수행하기 위해 char형 스택(s)을 선언해둔다.

 

3) ch의 길이만큼 다른 반복문을 수행하며 아래의 연산을 취한다.

- 현재 탐색값이 '[' 나 '(' 처럼 괄호의 앞부분이라면, s에 해당 문자를 push한다.

- 현재 탐색값이 ']' 나 ')' 처럼 괄호의 뒷부분이며 s의 top값이 각 괄호와 짝이 맞다면 s에 대하여 pop한다.

만일, 짝이 맞지 않는다면 괄호의 뒷부분이어도 s에 해당 문자를 push하도록 한다.

- 한 문장의 끝을 의미하는 .(점)이 탐색될 때까지 위 과정을 반복한다.

 

4) s가 비었다면 괄호의 짝이 알맞은 경우이므로, 이 경우에는 "yes"를 출력한다.

다만, s가 비어있지 않다면 괄호의 짝이 알맞지 않은 경우이므로, 이 경우에는 "no"를 출력한다.

 

5) 출력이 완료되었다면, 실행 종료한다.

반응형

 

성공한 코드

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

//백준 4949번 코드
int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);

	while (1) {
		string ch;
		getline(cin, ch);
		if (ch == ".") { break; }
		stack<char> s;
		for (int i = 0; i < ch.length(); i++) {
			if (ch[i] == '.') { break; }
			if (ch[i] == '[' || ch[i] == '(') { s.push(ch[i]); }
			else if (ch[i] == ']') {
				if (!s.empty() && s.top() == '[') { s.pop(); }
				else { s.push(ch[i]); }
			}
			else if (ch[i] == ')') {
				if (!s.empty() && s.top() == '(') { s.pop(); }
				else { s.push(ch[i]); }
			}
		}
		if (!s.empty()) { cout << "no" << endl; }
		else { cout << "yes" << endl; }
	}
}

 

제출 결과

(2022.02.06 백준 4949번 문제 제출 결과)