[백준] 10799번 쇠막대기 (C++)

문제

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

풀이

이 문제는 쇠막대기를 레이저로 자를 떄, 몇 개의 막대기가 나오는지 출력하는 문제이다.

 

입력은   ' ( ' , ' ) ' 두 가지이다.

' ( ' 뒤에 바로 ' ) '가 온다면 해당 자리에 레이저를 쏜다는 것이고, 이외의 입력은 막대기를 의미한다.

 

ex) "(())" 입력은 ㅡ ㅡ 처럼 막대기 2개가 나온다.

예제의 입력을 본다면 위 그림과 같이 17개의 막대기가 나온다.

 

 

해결 방법

스택을 이용하여 풀이했고 입력을 받은 뒤, 입력된 문자열을 탐색하면서 레이저를 감별하고 막대기를 자른다.

1. ' ( ' 이라면 bar 갯수를 + 1 한 뒤, 스택에 푸시한다. (flag 변수 true)
2. ' ) '이라면 막대기 끝 or 레이저이기 때문에 bar 갯수를 - 1 한다.
   1. flag 변수가 true일 때는 레이저이기 때문에 현재 bar 갯수를 sum에 더한 뒤, flag 변수를 false로 바꾼다.
   2. flag 변수가 false일 때는 막대기가 끝난 것이므로 sum + 1 한다.
   3. 스택에서 ' ( ' 를 팝한다.

#include <bits/stdc++.h>

using namespace std;

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);

	string input;
	cin >> input;

	int sum = 0, bar = 0;
	bool flag = false;
	stack<char> stack;
	
	for(int i = 0; i < input.length(); i++)
	{
		char c = input[i];
		if(c == '(')
		{
			bar ++;
			stack.push(c);
			flag = true;
		}
		else
		{
			bar--;
			if(flag) // 레이저일 때
			{
				sum += bar;
				flag = false;
			}
			else sum += 1;
			
			stack.pop();
		}
	}

	cout << sum ;
	return 0;
}