Commit dfa33ec

최대건수가 20만건이기 때문에 O(n)안에 끝내야 한다.

import java.io.BufferedReader;

import java.io.InputStreamReader;

import java.time.LocalDate;

import java.util.*;

class Main {

public static void main(String[] args) throws Exception {

BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

int n = Integer.parseInt(br.readLine());

String s = br.readLine();

Deque<Integer> stack = new ArrayDeque<>();

int maxLength = 0;

// 초기 인덱스를 스택에 추가하지 않음

for (int i = 0; i < s.length(); i++) {

if (s.charAt(i) == '(') {

stack.push(i); // 여는 괄호의 인덱스를 스택에 추가

} else {

if (!stack.isEmpty() && s.charAt(stack.peek()) == '(') {

stack.pop(); // 올바른 쌍을 만난 경우 스택에서 제거

int lastValidIndex = stack.isEmpty() ? -1 : stack.peek();

maxLength = Math.max(maxLength, i - lastValidIndex);

} else {

stack.push(i); // 닫는 괄호이지만 스택이 비어있거나 짝이 맞지 않는 경우 인덱스를 추가

}

}

}

System.out.println(maxLength);

}

}