15926 현욱은 괄호왕이야!!

다른 사람 블로그를 참고했다.

 

1. 풀이

 

<예시1>

5
(())(

 

일단 input 배열에 입력값을 받는다.

스택(stack)을 이용한다.

제일 먼저 stack에 -1을 넣는다.

이유는 나중에 알게 된다. 

 

규칙

1. input[i] 값 = ( 

=> stack에 i 값을 넣는다.

 

2. input[i] 값 = )

=> stack에서 값 하나를 꺼낸다.

  2-1. 이후에 만약 stack이 비어있으면, stack에 i 값을 넣는다.

  2-2. stack이 비어있지 않으면, i-stack.peek() 로 올바른 괄호 문자열 길이를 구한 뒤,

       올바른 괄호 문자열의 최대 길이를 다시 정해준다.

 

예시1을 가지고 자세히 살펴보자.

for 문을 이용한다.

 

1) i = 0 일때

 

문자열의 맨 처음은 (이다.

이때는 i 값을 stack에 집어넣는다.

그런데 맨 처음에 stack에는 -1 이 들어간다고 했다.

=> stack : -1,0

 

2) i =1

두 번째 문자는 ( 이다.

=> stack 에 1 집어 넣음

=> stack : -1,0,1

 

3) i =2

세 번째 값은 ) 이다.

=> stack 에서 값을 하나 꺼낸다.

=> stack : -1,0

 

이후에 올바른 괄호 문자열 길이를 구한다.

i =1 에서 문자는 ( 였다.

i =2 일때 ) 이므로

( ) 가 올바른 괄호 문자열로 완성된다. 그리고 이 길이는 2이다.

 

위에서 올바른 괄호 문자열 길이를 i-stack.peek() 로 구한다고 했다.

i = 2 이고, stack.peek() = 0 이다.

즉 길이가 2가 된다.

위에서 구한 길이와 같음을 알 수 있다.

 

4) i =3 

네 번째 값은 ) 이다.

=> stack 에서 값을 하나 꺼낸다.

=> stack: -1

 

=> 길이 : i -stack.peek() = 3 - (-1) = 4

첫번째부터 네번째까지 문자열을 살펴보면

( ( ) ) 이다.

올바른 괄호 문자열 길이가 4이다.

즉 위에서 구한 길이와 같음을 알 수 있다.

 

 

5) i = 4

다섯 번째 문자는 ( 이다.

=> stack에 4 집어 넣음

=> stack : -1, 4

 

 

올바른 괄호 문자열의 길이 중 최댓값은 4이며, 정답이 된다.

 

 

<예시2>

6

(()()(

 

맨 처음 stack 에는 -1 이 들어간다.

 

1) i =0 일때

문자는 ( 이다.

=> stack 에 0 집어넣음

=> stack : -1,0

 

2) i = 1 일때

문자는 ( 이다.

=> stack : -1,0,1

 

3) i = 2

문자는 ) 이다.

=> stack에서 값을 하나 꺼낸다.

=> stack : -1,0

 

올바른 괄호 문자열 길이 : i - stack.peek() = 2-0 = 2

올바른 괄호 문자열의 최대 길이 : 2

 

4) i = 3

문자는 ( 이다.

=> stack에 3을 넣는다.

=> stack : -1,0,3

 

5) i = 4

문자는 ) 이다.

=> stack에서 값을 하나 꺼낸다.

=> stack : -1,0

 

올바른 괄호 문자열 길이 : i - stack.peek() = 4 - 0 = 4

즉 입력값인 (()()( 에서

()() 부분이 올바른 괄호 문자열인데, 길이가 4이다.

 

 

6) i = 5

문자는 ( 이다.

=> stack 에 5를 집어 넣는다.

=> stack : -1,0,5

 

<예시 3>

5

())()

 

위에서 맨 처음 stack에 -1 을 넣는다고 했다. 그 이유를 여기서 알 수 있다.

 

1) i = 0

첫 번째 문자는 ( 이다.

=> stack에 0을 넣는다.

=> stack : -1,0

 

2) i = 1

문자는 ) 이다.

=> stack에서 값을 하나 꺼낸다.

=> stack : -1

 

길이 : i - stack.peek() = 1 - (-1) = 2

 

여기서 stack의 맨 처음 값 -1 이 쓰였다.

즉, ) 문자가 나왔을 때,

만약 앞에 ( 문자가 있었다면 올바른 괄호 문자열을 만들 수 있는데, 그 길이는  

( 의 인덱스가 아니라 ( 의 인덱스보다 먼저 stack에 들어가 있는 값으로 구해진다.

 

즉, 여기서 ( 의 인덱스는 0 이지만, 

길이를 구할 때 보면, -1, 즉 ( 의 인덱스 0 보다 먼저 stack에 들어간 -1 이 사용됨을 알 수 있다.

때문에 길이를 구하기 위해 -1 을 제일 앞에 넣은 것이다.

 

3) i = 2

문자는 ) 이다.

=> stack 에서 값을 꺼낸다.

=> stack 이 비어있다.

이 경우는 길이를 구하는 게 아니고, 그냥 i = 2 를 stack에 넣어주면 된다.

=> stack : 2

 

 

4) i = 3

문자는 ( 이다.

=> stack에 i = 3 을 넣는다.

=> stack : 2, 3

 

5) i = 4

문자는 ) 이다.

=> stack에서 값을 꺼낸다.

=> stack : 2

 

길이 : i - stack.peek() = 4 - 2 = 2

 

올바른 괄호 문자열 길이 중 최댓값은 2로 정답이다.

 

2. 최종 코드

 

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));
		int n = Integer.parseInt(br.readLine());
		String input [] = br.readLine().split("");
		
		Stack<Integer> stack = new Stack<>();
	
		int max = 0;
		stack.push(-1);
	
		for(int i=0; i<n;i++) {
			
			if(input[i].equals("(")) {
				stack.push(i);
				
			}else {
				stack.pop();
			
				if(stack.isEmpty()) {
					stack.push(i);
				
				}else {
						
				int length = i-stack.peek();
				max = Math.max(max, length);
				
			}
		  }
	   }
		
		System.out.println(max);
		
	}
}

 

 

참고 블로그 :

https://lms0806.tistory.com/48?category=873021 

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