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

 

정답코드

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


int main()
{
	string input;
	stack<char> s;
	getline(cin, input);

	int cnt = 0;

	for(int i=0; i< input.size(); i++)
	{
		if(input[i] == '(' && input[i+1] ==')')
		{
			cnt += s.size();
			i++;
		}
		else if(input[i] == '(')
		{
			s.push(input[i]);
		}
		else if(input[i] == ')')
		{
			cnt++;
			s.pop();
		}
	}
	cout << cnt << endl;
	return 0;
}

그려보지 않고서는 이해가지 않을 수 있습니다. () 이렇게 괄호 안에 아무것도 없이 만날 때는 쇠막대기를 쪼개는 것이고 그렇지 않을 경우 괄호 안에 (나 )가 포함되어 있는 경우에는 쇠막대기가 되는 구조입니다.

 

이 문제는 쇠막대기와 관련된 괄호 표현을 해석하는 문제입니다. 문제의 핵심은 주어진 괄호 문자열이 어떻게 쇠막대기의 개수와 관련되는지를 이해하는 것입니다.

 

문제 풀이 개념

1. 쇠막대기와 레이저의 표현:
   • (는 쇠막대기의 시작입니다.
   • )는 쇠막대기의 끝을 나타내기도 하지만, 바로 앞에 (가 있는 경우는 레이저를 나타냅니다.
   • 예를 들어, ()처럼 바로 붙어 있는 경우는 레이저입니다.
2. 레이저와 쇠막대기의 관계:
   • 레이저가 쇠막대기 위에 있을 때, 쇠막대기를 그 지점에서 자릅니다.
   • 예를 들어, 레이저 ()로 인해 현재 쇠막대기가 잘리면, 잘린 만큼의 조각이 생기게 됩니다.
3. 구조적으로 이해하기:
   • 여는 괄호 (는 스택에 쌓아가면서, 현재 레이저가 닿는 쇠막대기의 개수를 계산할 수 있습니다.
   • 레이저 ()가 등장할 때마다 스택에 쌓여 있는 (의 개수만큼 조각이 추가됩니다. 이는 레이저가 닿는 쇠막대기의 개수를 의미하니까요.
   • 닫는 괄호 )는 쇠막대기의 끝을 나타내고, 이 때는 조각이 하나 더 생깁니다 (왜냐하면 쇠막대기가 끝났으니까 그 끝부분이 조각이 되는 거죠).
4. 전체 흐름:
   • 문자열을 왼쪽부터 하나씩 보면서 (와 )를 처리합니다.
   • ()가 붙어 있으면 레이저로 판단하고, 현재 열린 모든 쇠막대기를 잘라 그 개수만큼 조각을 추가합니다.
   • (는 새로운 쇠막대기의 시작으로 보고 스택에 추가하여 추후 닫는 괄호가 나오면 이 쇠막대기를 닫을 수 있도록 합니다.
   • )는 쇠막대기의 끝이므로 조각을 하나 추가하고 스택에서 쇠막대기 시작을 빼줍니다.

이 과정으로 전체 문자열을 읽고 나면, 잘린 쇠막대기 조각의 총 개수를 얻게 됩니다.