[백준온라인] 15926번 현욱은 괄호왕이야!!

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

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

문제 요약 : 올바른 괄호 문자열을 구성하는 최대 길이 출력

입력	출력
1 ≤ N(문자 길이) ≤ 200000	가장 긴 올바른 괄호 문자열 길이 출력. () 는 올바른 괄호 문자열이다 어떤 문자열 x가 올바른 괄호 문자열이라면, (x)도 올바른 괄호 문자열이다. 어떤 문자열 x와 y가 올바른 괄호 문자열이라면, xy도 올바른 괄호 문자열이다.

JAVA

소스코드 : https://github.com/cbkpar/BOJ/blob/main/boj_15926.java

채점 번호	아이디	문제 번호	결과	메모리	시간	언어	코드 길이
31654337	cbkpar	15926	맞았습니다!!	24256KB	228ms	Java 11	749B

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,i,m,t;
		n = Integer.parseInt(br.readLine());
		boolean[] chk = new boolean[n];
		Stack<Integer> stack = new Stack<>(); 
		String str = br.readLine();
		for(i=0;i<n;i++) {
			if(str.charAt(i)=='(') {
				stack.add(i);
			}else {
				if(!stack.isEmpty()) {
					chk[stack.pop()] = true;
					chk[i] = true;
				}
			}
		}
		m = t = 0;
		for(i=0;i<n;i++) {
			if(chk[i]) {
				t++;
				m = Math.max(m, t);
			}else {
				t = 0;
			}
		}
		System.out.println(m);
	}
}

해당 위치 괄호가 올바른지 구분하는 n크기의 chk boolean배열을 초기화하고

주어진 문자열을 앞에서부터 확인하며

'('일 경우 스택에 해당 위치를 추가한다.

')'일 경우 스택이 비어있지 않다면 스택에서 위치를 하나 빼고

해당 위치와 비교한 문자열의 위치를 true로 설정해준다.

 

문자열을 모두 확인한 후에

chk배열에서 가장 길게 true값으로 나타나는 길이를 출력한다.

 

 

* 고칠점 )

')'의 문자열의 경우 스택에서 나온 값과 해당 위치 사이의 값은 항상 올바른 괄호이므로

두 위치 거리의 최댓값을 출력해도 된다.