문제
올바른 괄호 문자열이란 아래와 같이 정의된다.
- 빈 문자열은 올바른 괄호 문자열이다.
A가 올바른 괄호 문자열이면(A)도 올바른 괄호 문자열이다.A,B가 올바른 괄호 문자열이면AB도 올바른 괄호 문자열이다.
길이가 N인 괄호 문자열이 주어질 때, 가장 긴 올바른 괄호 부분 문자열의 길이를 구하는 프로그램을 작성하시오.
입력
첫째 줄에 문자열의 길이 N (1 ≤ N ≤ 1,000,000)이 주어진다.
둘째 줄에 길이가 N인 괄호 문자열이 주어진다.
출력
첫째 줄에 가장 긴 올바른 괄호 부분 문자열의 길이를 출력한다.
예제
입력 1
6
(()())출력 1
6입력 2
10
(()()))(())출력 2
6풀이
핵심 아이디어: 스택에 인덱스를 저장하면서 올바른 괄호 구간의 길이를 추적한다. 스택이 비어있을 때는 현재 인덱스를 경계 마커로 삼아 스택에 넣는다.
- 스택을 초기화하고
-1을 미리 넣는다. 이는 첫 번째 유효 구간의 시작 직전 경계를 나타낸다. - 문자열을 순회하면서:
(이면 현재 인덱스를 스택에 push한다.)이면 스택에서 pop한다.- pop 후 스택이 비어있으면 현재 인덱스를 새 경계 마커로 push한다.
- pop 후 스택이 비어있지 않으면 현재 인덱스 - 스택 top = 현재 올바른 괄호 부분 문자열의 길이이므로 정답을 갱신한다.
- 모든 문자를 처리한 후 정답을 출력한다.
스택 top이 마지막으로 짝이 맞지 않는 ) 의 인덱스를 가리키므로, 그 오른쪽부터 현재 인덱스까지의 구간이 유효한 괄호 문자열이 된다.
코드
package day399;
import java.util.*;
import java.io.*;
public class Day351BOJ15926괄호왕 {
public static void main(String[] args) throws 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);
}
}복잡도
- 시간: O(N) — 문자열을 한 번 순회하며 각 문자를 스택에 최대 한 번 push/pop
- 공간: O(N) — 스택에 최대 N개의 인덱스를 저장