[백준OJ] 10799번 쇠막대기

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

10799번: 쇠막대기

---

 

풀이

스택을 이용해도되고, 스택의 개념을 이용해 일반 변수를 선언하여 풀이를 해도된다.

 

1. 여는괄호를 만나면 파이프의 개수를 추가해준다.

 

2. 닫는괄호를 만나면, 레이저인지 아닌지를 판별해서 각 상황에 맞게 계산해준다.

 

2-1. 닫는괄호를 만났을때, 바로앞 괄호가 여는괄호라면, 레이저 이므로, 현재까지 만난 파이프에서 1을 빼준뒤, 정답에 현재 파이프값 만큼 더해준다. 현재까지 만난 파이프의 개수에서 -1을 해주는 이유는, 레이저의 열린괄호도 현재까지 만난 파이프에 포함이되므로, 레이저를 제외시켜주는것이다.

 

2-2. 닫는괄호를 만났을때, 바로앞 괄호가 닫는괄호라면, 하나의 파이프가 끝난다는 뜻이므로, 정답에 1개(끝나는 파이프의 꼬다리) 를 추가시켜준뒤, 현재까지 만난 파이프의 개수를 1 줄여준다.

 

시간복잡도

문자열을 한번만 탐색하면되므로, 문자열의 길이를 N이라 했을때, O(N)이 된다.

 

 

반응형

 

코드

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


int main() {
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	
	string str;
	cin >> str;

	int pipes = 0;
	int pieces = 0;
	for (int i = 0; i < str.size(); i++) {
		if (str[i] == '(') {
			pipes++;
		}
		else {
			//레이져일때
			if (str[i - 1] == '(') {
				pipes--;
				pieces += pipes;
			}
			//파이프 끝자락일때
			else {
				pipes--;
				pieces++;
			}
		}
	}
	cout << pieces;

	return 0;
}