백준 10799: 쇠막대기 [C++]

cozups·2022년 5월 15일
0

쇠막대기 규칙

  1. 레이저는 여는 괄호와 닫는 괄호의 인접한 쌍 ‘( ) ’ 으로 표현된다. 또한, 모든 ‘( ) ’는 반드시 레이저를 표현한다.
  2. 쇠막대기의 왼쪽 끝은 여는 괄호 ‘ ( ’ 로, 오른쪽 끝은 닫힌 괄호 ‘) ’ 로 표현된다.

레이저와 막대기를 어떻게 구분할까?
스택을 써야한다는 직감이 들었지만.. 어떻게해야 정답을 구할 수 있을지는 갈피를 잡지 못했다.

결과적으로는,

  1. 여는 괄호 '('를 만나면 스택에 넣는다.
  2. 닫는 괄호 ')' 를 만나면 이전의 문자를 확인한다.
  3. 이전 문자가 여는 괄호 '(' 였을 경우에는 스택의 사이즈를 더한다.
  4. 이전 문자가 닫는 괄호 ')' 였을 경우에는 막대기의 끝이라는 의미이므로 1을 더한다.
#include <iostream>
#include <stack> 

using namespace std;

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

	string str;
	stack<char> s;
	int ans = 0;

	cin >> str;

	for (int i = 0; i < str.length(); i++) {
		if (str[i] == '(') {
			s.push(str[i]);
		}
		else {
			char before = str[i-1];
			s.pop();

			if (before == '(') {
				ans += s.size();
			}
			else {
				ans += 1;
			}
		}
	}

	cout << ans;

	return 0;
}
profile
이제는 더 이상 물러날 곳이 없다

0개의 댓글