[백준] 북극곰은 괄호를 찢어 (25918번)

코드 힌트

1. 스택을 활용한 괄호 균형 확인:
   • 문자열을 순회하면서 스택을 사용해 괄호의 짝을 맞춥니다.
   • 열린 괄호는 스택에 추가하고, 닫힌 괄호가 스택의 top 괄호와 짝이 맞으면 스택에서 제거합니다.
2. 스택의 최대 크기 추적:
   • 스택의 현재 크기를 기록하여 괄호가 중첩된 최대 깊이를 추적합니다.
   • 문자열을 순회하면서 스택의 최대 크기를 업데이트합니다.
3. 유효성 검사:
   • 문자열 순회 후 스택이 비어있지 않다면 올바른 괄호 문자열이 아니며, 결과를 -1로 설정합니다.
4. 스택의 깊이 계산:
   • 각 단계에서 스택의 크기를 계산하여 최대값을 업데이트합니다.

 

---

정답은 더보기 클릭

import java.util.*;

class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        
        int n = Integer.parseInt(in.nextLine()); // 괄호 문자열의 길이 입력 (현재 사용하지 않음)
        
        String bracket = in.nextLine(); // 괄호 문자열 입력
        
        Stack<Character> stk = new Stack<>(); // 괄호를 저장할 스택
        int result = 0; // 최대 괄호의 깊이
        
        // 문자열의 각 문자에 대해 반복
        for (char c : bracket.toCharArray()) {
            // 스택이 비어있지 않고 O, X 조건일 때 스택에서 제거
            if (!stk.isEmpty() && (stk.peek() == '(' && c == ')' || stk.peek() == ')' && c == '(')) {
        		stk.pop();
        	}
            // 짝이 맞지 않으면 현재 괄호를 스택에 추가
            else {
                stk.push(c);
            }
            // 현재 스택의 크기와 최대 크기를 비교하여 업데이트
            result = Math.max(result, stk.size());
        }
        
        // 스택이 비어있지 않으면 올바른 괄호 문자열이 아님
        if (!stk.isEmpty()) {
            result = -1;
        }
        
        System.out.println(result); // 최대 괄호의 깊이나 -1을 출력
    }
}