[백준 BOJ] 11899번 괄호 끼워넣기 (C++/cpp)

문제 설명

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

11899번: 괄호 끼워넣기

 

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

백준의 11899번 문제는 스택을 이용한 연산을 통해 해결해야 하는 문제이다.

해당 문제는, 주어진 입력값에 대하여 삽입이 필요한 괄호의 개수를 출력해야 하는 문제이다.

괄호에 관한 문제는 주로 스택을 이용해야 하는 문제인데, 스택의 응용이 아직 어색하다면 아래의 링크를 참고해보길 바란다.

해당 문제보다는 다소 난이도가 낮은 문제이지만 이용하는 원리 자체는 유사하다.

https://smary-it.tistory.com/63

[백준 BOJ] 9012번 괄호 (C++/cpp)

필자는 여기서 괄호가 성립되는 조건을 우선적으로 생각하며 코드를 구성해보았다.

이때 괄호는 '(' 다음에 ')'가 와야 한 쌍이 되기 때문에, 이미 쌍이 맞는 괄호를 제외하는 연산을 통해 해결할 수 있었다.

더 자세한 설명은 아래에 기재해놓으니 혹여나 해당 문제를 해결하는 데에 어려움을 겪고 있다면 아래의 설명과 코드를 참고해보길 바란다.

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

 

코드의 실행 순서

1) 괄호로 구성된 문자열(st)을 입력받는다.

 

2) 연산을 위한 스택(s)을 char형으로 선언해둔다.

 

3) st의 길이만큼 반복문을 실행하여 아래의 연산을 취한다.

- 현재 탐색 중인 배열값을 s에 push한다.

- 다만, 현재 위치의 괄호 요소와 현재 스택의 top의 괄호 요소가 한 쌍을 이룬다면, push하지 않고 pop 연산을 취한다.

=> 이렇게 하면, 한 쌍을 이루지 못한 괄호만 스택에 쌓이게 될 것이다.

 

4) 모든 연산이 완료되었다면, 최종적으로 이루어진 s의 크기를 출력한 뒤 실행 종료한다.

(s의 크기는 즉, 한 쌍을 이루지 못한 괄호의 개수를 뜻한다.)

반응형

 

성공한 코드

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

//백준 11899번 코드
int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);	cout.tie(NULL);

	string st;
	cin >> st;

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

 

제출 결과

(2022.04.26 백준 11899번 문제 제출 결과)