백준 15926 현욱은 괄호왕이야!! C++

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

15926번: 현욱은 괄호왕이야!!

---

문제

여는 괄호 ‘(’와 닫는 괄호 ‘)’로 구성된 문자열에서 아래의 조건을 만족하는 문자열을 올바른 괄호 문자열이라고 부른다.

1. () 는 올바른 괄호 문자열이다
2. 어떤 문자열 x가 올바른 괄호 문자열이라면, (x)도 올바른 괄호 문자열이다.
3. 어떤 문자열 x와 y가 올바른 괄호 문자열이라면, xy도 올바른 괄호 문자열이다.

현욱은 친구로부터 생일 선물로 굉장히 긴 괄호 문자열을 받았다(도대체 왜 이런 걸 선물하는걸까?). 하지만 현욱은 올바른 괄호 문자열이 아니면 굉장히 싫어하기 때문에, 받은 괄호 문자열에서 연속한 일부분을 잘라서 올바른 괄호 문자열을 만들려고 한다. 그리고 이왕이면 긴 문자열이 좋으니 현욱은 부분 구간을 최대한 길게 잘라내려고 한다. 현욱을 도와 주어진 괄호 문자열에서 위의 조건을 만족하는 가장 긴 부분 문자열의 길이를 계산하는 프로그램을 작성해보자.

---

입력

첫 줄에 문자열의 길이 n (1 ≤ n ≤ 200,000)이 주어진다.

둘째 줄에 괄호로만 구성된 길이 n짜리 문자열이 주어진다.

---

출력

주어진 문자열에서 길이가 가장 길면서 올바른 괄호 문자열인 부분 문자열의 길이를 출력한다. 올바른 괄호 문자열인 부분 문자열을 찾을 수 없는 경우 0을 출력한다

---

이문제도 굉장히 많이 제출했ㄷ..

5달전!

---

먼저 () 이렇게 쌍이 맞는 괄호는 올바른 문자열이라고 하고, 올바른 문자열을 여러개 이어붙은 문자열도 올바른 문자열입니다.

 

다른분들의 코드를 참고했고, 다음과 같은 과정으로 진행됩니다.

 

먼저, pair형태의 스택을 하나 선언합니다(문자열과 정수). 이 스택은 문자열의 문자 ( or ) 와 인덱스를 갖을 스택입니다.

그리고 bool형태의 배열을 하나 선언해줍니다. 이 배열은 인덱스가 올바른 문자열이면 true를, 

올바르지 않은 문자열이라면 false를 갖습니다.

 

stack<pair<char,int>> st;
bool index[200001];
int n;
string str;

그 후, n과 입력 문자열을 입력받아주고,

void init(){
	cin >> n;
	cin >> str;	
}

 

가장 긴 올바른 괄호 문자열의 길이를 반환하는 함수가 실행됩니다.

이 함수의 과정은 다음과 같습니다.

 

1) 입력받은 문자열의 길이만큼 for문을 돌면서 스택이 비어있다면 {문자,for문의 인덱스} 를 스택에 넣습니다.

2) 스택이 비어있지 않고 괄호가 짝이 맞는다면, 스택의 Top이 ( 이고, 현재 문자열의 문자가 ) 라면

 

스택의 Top에 있는 index -> stack,top().second를 가져와서 bool 배열에 해당 인덱스를 True로 바꿔주고,

현재 인덱스도 True로 바꿔줍니다.

 

3) 그 외의 경우에는 스택이 비어있을 떄와 마찬가지로 스택에 넣어주면 됩니다.

for(int i = 0;i<str.size();i++){
		if(st.empty()){ //비어있는 경우 {문자,인덱스} PUSH 
			st.push({str[i],i});
		}
		else{
			//짝이 맞는 경우
			/* Top의 index를 방문처리, 현재 인덱스 방문처리 (올바른 문자열) */ 
			if(st.top().first == '(' && str[i] == ')'){
				int valid_index = st.top().second;
				index[valid_index] = true;
				index[i] = true;
				st.pop();
 
			}
			else{
				st.push({str[i],i});
			}
		}
	}

 

이제 , 문자열을 넣는 벡터를 하나 선언해주고,

for문을 N만큼 돌면서, bool형 배열이 True라면 벡터에 넣습니다.

만약 bool형 배열이 False라면, 현재 가장 긴 올바른 괄호 문자열의 길이와 비교해서 벡터의 크기가 크다면

값을 갱신해주고, 벡터를 지워줍니다.

 

for(int i = 0;i<n;i++){
		if(index[i] == true){ 
			v.push_back(str[i]);
		}
		else if(index[i] == false){ //answer보다 크다면 값의 갱신
			if(v.size() > answer){
				answer = v.size();
				
			}
            v.clear(); //벡터를 지워줌 (올바르지 않은 문자열)
		}
	}

---

이떄, 마지막으로 벡터에 있는 값과 한번 더 비교를 해줘서 갱신을 마지막으로 해주고,

answer를 넘겨주면 됩니다.

 

 

전체 소스 코드->

#include <iostream>
#include <stack>
#include <vector>
#include <string>
 
using namespace std;
 
stack<pair<char,int>> st;
bool index[200001];
int n;
string str;
 
void init(){
	cin >> n;
	cin >> str;	
}
 
int calculate_long_str(){
	int answer = 0;
	for(int i = 0;i<str.size();i++){
		if(st.empty()){ //비어있는 경우 {문자,인덱스} PUSH 
			st.push({str[i],i});
		}
		else{
			//짝이 맞는 경우
			/* Top의 index를 방문처리, 현재 인덱스 방문처리 (올바른 문자열) */ 
			if(st.top().first == '(' && str[i] == ')'){
				int valid_index = st.top().second;
				index[valid_index] = true;
				index[i] = true;
				st.pop();
 
			}
			else{
				st.push({str[i],i});
			}
		}
	}
 
	vector<char> v;
 
	for(int i = 0;i<n;i++){
		if(index[i] == true){
			v.push_back(str[i]);
		}
		else if(index[i] == false){
			if(v.size() > answer){
				answer = v.size();
				
			}
            v.clear();
		}
	}
    
    if(v.size() > answer){
        answer = v.size();
    }
 
	return answer;
 
}
 
int main(void){
	init();
	cout << calculate_long_str();
}