문제 출처

1. 문제설명

• 쇠막대기를 레이저로 절단하려고 한다.
• 효율적인 작업을 위해 다음 조건을 만족한다.
  • 쇠막대기는 자신보다 긴 쇠막대기 위에만 놓일 수 있다.
    • 다른 쇠막대기 위에 놓는 경우 완전히 포함되지만, 끝점은 겹치지 않도록 놓는다.
  • 각 쇠막대기를 자르는 레이저는 적어도 하나 존재한다.
  • 레이저는 어떤 쇠막대기의 양 끝점과도 겹치지 않는다.
• 레이저는 여는 괄호와 닫는 괄호의 인접한 쌍 ‘( ) ’ 으로 표현된다. 또한, 모든 ‘( ) ’는 반드시 레이저를 표현한다.
• 쇠막대기의 왼쪽 끝은 여는 괄호 ‘ ( ’ 로, 오른쪽 끝은 닫힌 괄호 ‘) ’ 로 표현된다.

2. 알고리즘 설계

• 스택을 활용한 문제이다.
  • 모든 점이 겹치지 않으면서, 괄호…
  • 스택…문제
• 여는 소괄호라면 push한다.
• 닫는 소괄호라면,
  • 이전 위치의 소괄호가 여는 소괄호 였다면, 쇠막대기가 잘린 것이므로 현재 스택에 크기만큼 정답값 더한다.
    • 쇠막대기가 끝나지 않았고, 잘려졌다면, 두동강 난 것이다.
  • 그렇지 않다면, 정답값에 1을 더한다.
    • 레이저가 끝나는 부분이므로, 무조건 쇠막대기가 1조각 남기 때문이다.

3. 전체 코드

#include <bits/stdc++.h>
using namespace std;

int main(void)
{
	ios::sync_with_stdio(false);
	cin.tie(NULL);

	int ans = 0;
	string str;
	cin >> str;

	stack<char> st;
	for (int i = 0; i < str.size(); i++) {
		if (str[i] == '(') st.push('(');
		else {
			if (str[i - 1] == '(') {
				st.pop();
				ans += st.size();
			}
			else {
				st.pop();
				ans++;
			}
		}
	}

	cout << ans;
}

4. 소감

• 앞서 언급한,
• 연속으로 닫는 괄호일 때,
• 여는 괄호 다음 닫는 괄호일 때,
• 각각의 처리 로직을 이해하면 간단한 풀이였다.