BOJ 10799 - 쇠막대기

쇠막대기 - 🥈 Silver 3

• 문제 링크
  https://www.acmicpc.net/problem/10799

Stack의 개념을 활용하여 풀 수 있는 문제다.

열린 괄호일 경우에는 스택에 push하고, 닫힌 괄호일 경우에는 스택에 들어있는 열린 괄호를 pop하여 풀이하는 것은 다른 stack관련 문제와 동일하나, 닫힌 괄호일 경우를 구분해주는 것이 관건이다.

닫힌 괄호일 경우는 크게 2가지이다.

1. 레이저일 경우
2. 쇠막대기가 끝났음을 알리는 경우

레이저일 경우에는 ()으로 표시하므로, 바로 전 문자가 (일 경우로 생각하면 된다. 레이저를 표시하는 열린 괄호 하나를 제외한 나머지가 잘려나간 쇠파이프의 개수를 의미하므로 이를 더해준다.

반대로 쇠막대기의 끝을 알리는 닫힌 괄호일 경우에는 이전 문자열이 )이다. 이 경우에는 단순히 1만 쇠파이프의 개수에 더해주면 된다.

풀이 코드

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

int main() {
	// 주어지는 input값 저장
	string input;
	cin >> input;

	// 잘려진 막대기의 개수를 저장할 변수 생성 + 초기화
	int counter = 0;

	// 괄호를 넣고 빼면서 막대기의 개수를 count하기 위한 stack 생성
	stack<char> s;

	// 입력받은 문자열을 처음부터 끝까지 탐색
	for (int i = 0; i < input.length(); i++) {

		// 열린 괄호일 경우 stack에 저장
		if (input[i] == '(') {
			s.push('(');
		}

		// 닫힌 괄호일 경우
		else {
			// 이전 괄호도 닫힌 괄호일 경우 처리
			if (input[i - 1] == ')') {
				s.pop();
				counter += 1;
			}
			// 이전 괄호가 열린 괄호일 경우 처리
			else if (input[i - 1] == '(') {
				s.pop();
				counter += s.size();
			}
		}
	}
	// 결과값 출력
	cout << counter << endl;

	// 프로그래밍 종료
	return 0;
}

결과

• 참고
  https://hsp1116.tistory.com/29