[백준] 15926번 : 현욱은 괄호왕이야!!(JAVA)

 

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

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

풀이

괄호를 입력받고 그 괄호 중 올바른 괄호의 최대 길이를 출력해주는 문제입니다.

ex) () -> 2
()(()) -> 6

(())) -> 4

 

stack에 처음에는 아무것도 없으므로 -1을 넣은 상태로 시작합니다.

(이 들어오면 (의 위치를 스택에 넣어줍니다.

)이 들어오면 (을 꺼내고 스택이 비어있지 않으면 answer과 현재위치 - stack에 있는 수 중 큰 값을 answer에 넣어줍니다.

비어있으면 올바르지 않은 문자이므로 stack에 위치를 넣어줍니다.

ex) (())

stack : -1

stack : -1, 0 (

stack : -1, 0, 1 ((

stack : -1, 0 (() answer = 2 - 0 = 2

stack : -1 (()) answer = max(2, 3 - - 1) = max(2, 4) = 4

 

소스코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Stack;

public class Main {
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); 
		
		Stack<Integer> stack = new Stack<>();
		br.readLine();
		
		stack.add(-1);
		
		int answer = 0;
		String s = br.readLine();
		for(int i = 0; i < s.length(); i++) {
			char ch = s.charAt(i);
			if(ch == '(') {
				stack.add(i);
			}
			else {
				stack.pop();
				if(!stack.isEmpty()) {
					answer = Math.max(answer, i - stack.peek());
				}
				else {
					stack.add(i);
				}
			}
		}
		System.out.print(answer);
	}
}