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

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

 

알고리즘 분류

자료구조
스택

 

---

Hint

 

굳이 STL stack 을 사용하지 않아도

Stack 논리를 활용하여 풀 수 있습니다

 

---

Solution

 

) 나왔을 때

직전에 ( 나오면 자르기 -> 스택에서 -1 그리고 스택 내 남은 아이템 개수만큼 카운트 +

직전에 ) 나오면 -> 스택에서 -1 카운트 +1

( 나오면 스택에 +1

Stack: 1

예제1)
3+3+1+3+1+2+1+1+1+1
= 17

 

 

#include <iostream>
#include <cstring>

using namespace std;
int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(NULL);
	int stack_size = 0; // 실제 스택을 구현할 필요는 없으므로 stack_size를 int형으로 구현
	char ch[100001]; // 문자열 받기
	long long int count = 0; // 총 개수
	cin >> ch;
	int ch_len = strlen(ch); // cstring 필요

	stack_size++; // 첫 입력은 '(' 임이 확정

	for (int i = 1; i < ch_len; i++) {
		if (ch[i] == '(') {
			stack_size++;
		}
		else { // ')'이 입력
			if (ch[i-1] == '(') { // 이전 입력이 '('
				stack_size--;
				count += stack_size;
			}
			else { // 이전 입력이 ')'
				stack_size--;
				count++;
			}
		}
	}
	std::cout << count;
}

알고리즘 자체는 어렵지 않은데

입출력의 문제가 좀 까다로운 편입니다