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

코드

#define _CRT_SECURE_NO_WARNINGS
#include <iostream> 
#include <limits.h>
#include <algorithm>
#include <string>
#include <vector>
#include <math.h>
#include <cmath>
#include <cstring>
#include <queue>
#include <stack>
#include <functional>
using namespace std;

int main() {

	stack<char> stack;

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

	for (int i = 0; i < str.length(); i++) {
		if (str[i] == '(') { //여는 괄호면 push
			stack.push(str[i]);
		}
		else {
			stack.pop();
			if (str[i - 1] == '(') { //레이저인 경우 
				result += stack.size(); //사이즈만큼 갯수 추가 
			}
			else { //파이프끝 이면 
				result++;
			}
		}
	}

	cout << result;

	return 0;
}

풀이

스택을 써야한다는건 알겠고 (뒤에 )가 나올때가 1 레이저일경우 2 쇠막대기의 끝일 경우 이렇게 나눠서 접근해야한다는것도 알았다 근데 이제 갯수를 어떻게 세야할지 너무 모르겠더라 큼

알고보면? 되게 간단한건데 이 계산을 어떻게 해야할지에서 막막했다

레이저일경우와 쇠막대기의 끝일경우 각각 계산방법이 다르다

공통적으로 같은건 )가 오면 pop을 한다는 것이다( ')'를 pop하는게 아님)

1. 레이저일경우

레이저일 경우는 (바로 다음 )가 오는 경우이다

일단 )가 오니까 (를 pop한다 

그리고 바로 앞에 괄호를 본다 (이니까 레이저의 경우이다

이때는 스택의 사이즈만큼 갯수를 추가한다 .size()메서드를 쓰면 됨 

총 ( ( ( 3번 푸쉬했으니까 사이즈만큼 3이 추가된다

 

2. 쇠막대기의 끝인경우

그림의 8번까지 보면 레이저가 바로 연속으로 하나 더 나온다 이때 역시 스택의 사이즈는 3이라서 총 6이 된다

그리고 쇠막대기의 끝인 경우가 나온다

9번째에 ) 가 나오고 바로앞에가 )라서 쇠막대기의 경우인걸 알 수 있다

이때는 그냥 pop을하고  +1을 더해주면 된다

그럼 7이 되고 ( ( ( 여기서 3번째 (이거는 pop이 되니까 사라진다 

 

 

계산방법만 알면 금방 풀 수 있을듯

출처 

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

10799번: 쇠막대기