[백준 15926] 현욱은 괄호왕이야!! (C++, Java)

문제 링크: https://www.acmicpc.net/problem/15926

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

1. 주의할 점

- 스택을 사용해서 해결한다 → O(N)에 해결

 

2. 구현

- 스택에 문자와 문자가 위치했던 인덱스 번호를 구조체 형태로 저장하여 쌓는다

- 이때, 스택의 Top에 위치한 원소와 현재 검색하려는 원소가 쌍이라면 스택의 원소를 뺀다

- 이외의 경우에는 스택에 원소를 추가한다

- 위의 방법을 통해 스택에는 쌍을 못이룬 문자들에 대한 정보만 담고 있다

- 쌍을 못 이룬 문자들이 위치한 인덱스를 바탕으로 인덱스의 차를 이용하여 가장 긴 올바른 괄호의 길이를 구한다. 이때, 첫 길이는 문자열의 길이 - 스택의 Top으로 설정한다

 

[C++]

#include <iostream>
#include <string>
#include <algorithm>
#include <stack>
using namespace std;
struct info{
    char c;
    int idx;
};

int main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    int num,answer=0;
    string str;
    cin>>num>>str;
    stack<info> s;
    
    for(int i=0;i<num;i++){
        char c = str[i];
        if(s.empty()){
            s.push({c,i});
            continue;
        }
        char topChar = s.top().c;
        if(topChar=='(' && c==')') s.pop();
        else s.push({c,i});
    }
    int temp = num;
    while(!s.empty()){
        int idx = s.top().idx;
        int diff = temp-idx-1;
        if(diff>1) answer = max(answer, diff);
        temp=idx;
        s.pop();
    }
    answer = max(answer,temp);
    cout<<answer;
    return 0;
}

 

 

[Java]

import java.util.*;
import java.lang.*;
import java.io.*;

class Main {
	public static void main (String[] args) throws java.lang.Exception {
	    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	    int num = Integer.parseInt(br.readLine());
	    String str = br.readLine();
	    Stack<Integer> s = new Stack<>();
	    s.add(-1);
	    int answer = 0;
	    for(int i=0;i<num;i++){
	        char c = str.charAt(i);
	        if(c=='(') s.add(i);
	        else{
	            s.pop();
	            if(s.empty()){
	                s.add(i);
	                continue;
	            }
	            int idx = s.peek();
	            answer = Math.max(answer,i-idx);
	        }
	    }
		System.out.print(answer);
	}
}