백준 24552번 ) 올바른 괄호 (java)

https://www.acmicpc.net/problem/24552

24552번: 올바른 괄호

 

문제

 

풀이

누적합으로 푸는 문제라고 하는데, 나는 배열로 저장하지는 않고 int 에서 +, -로 풀었다.

먼저 입력받은 문자열에서 총 여는 괄호와 닫는 괄호의 개수를 확인한다.

둘 중 어떤 괄호의 개수가 더 많은지 확인 후, ( 괄호의 개수가 많을 경우 왼쪽에서부터 확인하면서 올바른 괄호가 완성된 이후부터 ( 개수를 count 해서 출력한다.

) 괄호의 개수가 많은 경우, 반대로 오른쪽부터 확인하면서 올바른 괄호가 완성된 이후부터 ) 의 개수를 count 한다. (이 중 어느 괄호를 삭제해도 올바른 괄호가 완성되기 때문!)

 

 

코드

import java.io.*;

public class Main {
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String s = br.readLine();
        int left=0, right=0, sum=0;

        for(int i=0; i<s.length(); i++){
            if(s.charAt(i) == '('){
                left++;
            } else{
                right++;
            }
        }

        if(left>right){
            left = 0;
            right = 0;
            for(int i=0; i<s.length(); i++){
                if(s.charAt(i) == '(') left++;
                else right++;
                if(left == right){
                    left = 0;
                    right = 0;
                }
            }
            System.out.println(left);
        }
        else {
            left = 0;
            right = 0;
            for(int i= s.length()-1; i>=0; i--){
                if(s.charAt(i) == '(') left++;
                else right++;
                if(left == right){
                    left = 0;
                    right = 0;
                }
            }
            System.out.println(right);
        }
    }
}

 

 

풀면서 생각보다 단순한 문제이나, 어떤 방식으로 사고해서 풀어야하는지 찬찬히 생각해야함이 어려웠다.

특히 ')' 괄호의 경우 오른쪽부터 확인해야함을 잘 알아두자! (왼쪽부터 카운트하면 올바른 괄호로 잘못 카운트할 수 있음.)