백준 10799. 쇠막대기

쇠막대기

스택 응용 문제

쇠막대기를 겹쳐 자를때, 몇개가 나올지 계산하는 문제

1. 간단 설명

---

간단히 설명하면

쇠막대기를 겹쳐서 숭덩숭덩 잘랐을 때, 쇠막대기의 개수를 구하는 문제

()는 레이저, (는 쇠막대기 시작, )는 쇠막대기 끝 이라고 생각하면 쉽다

2. 문제 분석

---

첫번째 예시를 설명하면

1. 첫번째 ()는 허공에 레이저를 발사한 것

2. 이후 (((는 쇠막대기 3개를 겹친걸 표현

3. ()로 레이저 커팅하여 3개의 쇠막대기를 얻음

1. 또 ()로 커팅해서 3개의 쇠막대기를 더 얻음

1. ) 가장 위에있는 쇠막대기 끝

이런식으로 레이저를 쐈을 때는, 겹쳐진만큼 쇠막대기 개수만큼 막대가 추가되고

)를 만났을 때는 막대가 짜투리 한개만 추가되는 것을 알 수 있다

이를 스택을 이용해 (을 차곡차곡 쌓다가, )를 만났을 때

레이저인지, 막대의 끝인지 구분하여 막대의 개수를 더해주면 된다

필요 변수

• 입력받을 문자열 input (최대 100,000 길이)
• 문자열의 각 문자를 저장할 stack
• 구하고자 하는 전체 쇠막대기 개수 int result

알고리즘

1. 문자열 입력받기
2. 문자열의 처음부터 끝까지 순회
	2-1. 현재 문자가 `(`라면 막대의 시작이므로, 스택에 넣는다
	2-2. 현재 문자가 `)`라면, 
		2-2-1. 레이저라면 (이전 문자 확인 필요), 전체 막대개수에 현재 겹쳐진 막대 개수를 더해준다
		2-2-2. 레이저가 아니라면, 막대 하나를 추가한다
3. 전체 막대 개수 출력 후 종료

3. 소스코드

---

#include <iostream>
#include <stack>

using namespace std;

int main() {
	// freopen_s(new FILE*, "input.txt", "r", stdin);
	string input; cin >> input;

	stack<char> st;
	int result = 0;

	for (int i = 0; i < input.size(); i++) {
		if (input[i] == '(') {
			st.push(input[i]);
		}
		else {
			st.pop();
			if (input[i - 1] == '(') {
				result += st.size();
			}
			else {
				result++;
			}
		}
	}

	cout << result;


	return 0;
}