문제

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

풀이

시간 초과

가장 떠올리기 쉬운 방법은 레이저 위치를 미리 표시해두고 괄호 쌍이 만들어질 때마다 그 사이에 있는 레이저 개수에 1을 더하여 절단된 쇠막대기 개수를 구하는 것이다. 그리고 그 개수를 모두 합하면 정답이 될 것이다.

#include <iostream>
#include <string> 
#include <cstring>
#include <sstream>
#include <algorithm>
#include <vector>
#include <cmath>
#include <stack>
#include <queue>
#include <map>
#include <set>
#include <unordered_set>
#include <unordered_map>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;

int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);

	string input; 
	cin >> input; 

	string laser = "()";
	string::size_type pos = input.find(laser);

	// 레이저의 위치 표시 
	while(pos != string::npos){
		input.replace(pos, laser.size(), "l");
		pos = input.find(laser);
	}
	
	stack<int> st;
	int answer = 0;
	
	for(int i = 0; i < input.size(); i++){
		char ch = input[i];
		if(ch == '('){
			st.push(i);
		}else if(ch == ')'){
			int start = st.top(); 
			int end = i; 
			st.pop();

			// start ~ end 사이의 레이저 개수 
			int tmp = 0; 
			for(int j = start; j <= end; j++){
				if(input[j] == 'l') tmp++; 
			}

			// 쇠막대기 개수 갱신 
			answer += tmp + 1; 
		}
	}

	cout << answer; 
	
	return 0;
}

하지만 문자열의 최대 크기가 10만이므로 위와 같이 이중 반복문으로 풀면 O(N^2)이어서 시간초과가 발생할 수밖에 없다.

1. 입력 문자열을 순차 탐색하면서 괄호 쌍을 찾는다. - O(N)
2. 그 괄호 쌍 사이에 있는 레이저 개수도 순차 탐색으로 구한다. - O(N)

이보다 더 효율적인 방법을 생각해야 한다.

코드 개선

쇠막대기가 언제 절단되는지 다시 한번 생각해보자. 아직 열린 괄호만 나온 상태에서 레이저가 등장하면 해당 쇠막대기들은 줄줄이 절단될 수밖에 없다.

그러다가 닫힌 괄호가 나오면 가장 가까운 레이저와 닫힌 괄호 사이의 막대기가 하나 더 나온다.

즉, 레이저가 등장할 때마다 스택에 저장된 열린 괄호의 개수만큼 막대기가 절단되는 것이다. 닫힌 괄호가 나왔을 때는 1개만 증가시키면 된다.

#include <iostream>
#include <string> 
#include <cstring>
#include <sstream>
#include <algorithm>
#include <vector>
#include <cmath>
#include <stack>
#include <queue>
#include <map>
#include <set>
#include <unordered_set>
#include <unordered_map>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;

int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);

	string input; 
	cin >> input; 
	
	stack<char> st;
	int answer = 0;

	for(int i = 0; i < input.size(); i++){
		char ch = input[i];
		if(ch == '('){
			st.push(ch);
		}else{
			// 레이저인 경우 
			if(input[i - 1] == '('){
				st.pop(); // 레이저의 열린 괄호 제거 
				answer += st.size(); // 남은 열린 괄호의 개수 
			}else{
				// 그냥 닫힌 괄호인 경우 
				answer++;
				st.pop(); // 가장 최근에 들어간 괄호 제거 
			}
		}
	}

	cout << answer; 
	
	return 0;
}

시간복잡도 O(N)에 해결할 수 있다!!