10799 쇠막대기 with C++

문제

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

10799번: 쇠막대기

해결한 방법

1. 레이저가 지나가는 막대기 수를 num_add로 정의하고 총 막대기의 개수를 num_bar로 정의했습니다.
2. '(' 다음 '('가 알려주는 것은 이전 '('이 막대기라는 것입니다. 따라서 총 막대(num_bar)에 +1 동강나는 막대기 수(num_add)에도 +1을 해줍니다.
3. '(' 다음 ')'는 레이저를 의미합니다. 막대기 동강내기 실행
4. ')' 다음 '('는 아직 어떤 것인지 모릅니다 하지만 '('가 나왔다는 것은 알 수 있습니다. isBeforeLeft = 1;
5. ')' 다음 ')'는 막대기의 끝을 의미합니다. 동강나는 막대기 수가 줄어들었습니다. num_add--;

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

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

	string inp_str;
	cin >> inp_str;
	
	bool isBeforeLeft = false;
	int num_bar = 0;
	int num_add = 0;
	for (int i = 0; i < inp_str.size(); i++) {
		if (isBeforeLeft) {
			if (inp_str[i] == '(') {	// 새로운 막대기
				num_bar++;
				num_add++;
			}
			else {	// 레이저
				isBeforeLeft = false;
				num_bar += num_add;
			}
		}
		else {
			if (inp_str[i] == '(') {	// 막대기 또는 레이저의 시작부분
				isBeforeLeft = true;
			}
			else {	// 막대기 끝
				isBeforeLeft = false;
				num_add--;
			}
		}
	}
	cout << num_bar << "\n";

	return 0;
}

배운 점

원래 최초 코드는 string이 아닌 char 배열로 입력을 받고 '\0'을 만나면 for문을 빠져나오는 코드를 작성했는데 string이 더 빨라서 string으로 고쳤습니다.

 

알고리즘 분류에 stack이 있어서 stack으로 풀려다가 num_add가 stack의 역할을 하는 것을 알게되었습니다.