[Gold IV] 올바른 괄호 - 24552

문제 링크

성능 요약

메모리: 15868 KB, 시간: 148 ms

분류

누적 합

제출 일자

2025년 5월 16일 00:43:59

문제 설명

$\texttt{(, )}$로 구성된 문자열 $S$에서 정확히 하나의 괄호를 지워 올바른 괄호열을 만들 수 있는 경우의 수를 출력하자.

올바른 괄호열은 다음과 같이 정의된다.

1. ()는 올바른 괄호열이다.
2. A가 올바른 괄호열이면 (A)는 올바른 괄호열이다.
3. A와 B가 올바른 괄호열이면 AB는 올바른 괄호열이다.

입력

첫번째 줄에 문자열 $S$가 공백 없이 주어진다. ($3 \leq \vert S \vert \leq 100\,000$, $\vert S \vert$는 홀수이다.)

답은 $1$ 이상이다. 즉, 지웠을 때 올바른 괄호열이 되는 문자가 적어도 하나 존재한다.

출력

올바른 괄호열을 만들 수 있는 경우의 수를 출력한다.

문제 풀이

( 가 1개 많거나 ) 가 1개 많을 수 밖에 없다.

• ( 가 많을때 왼쪽에서 오른쪽으로 진행. 음수 나오면 x, 0이상 나오도록 진행

• ) 가 많을때 오른쪽에서 왼쪽으로 진행. 음수 나오면 x, 0이상 나오도록 진행

코드

package BOJ_24552_올바른괄호;

/**
 * Author: nowalex322, Kim HyeonJae
 */

import java.io.*;
import java.util.*;

public class Main {
    static BufferedReader br;
    static BufferedWriter bw;
    static StringTokenizer st;

    public static void main(String[] args) throws Exception {
        new Main().solution();
    }

    public void solution() throws Exception {
//        br = new BufferedReader(new InputStreamReader(System.in));
        br = new BufferedReader(new InputStreamReader(new FileInputStream("src/main/java/BOJ_24552_올바른괄호/input.txt")));
        bw = new BufferedWriter(new OutputStreamWriter(System.out));

        String str = br.readLine();
        int N = str.length() / 2 + 1;
        int cnt = 0;
        for(int i=0; i<str.length(); i++) {
            if(str.charAt(i)=='(') cnt++;
            else cnt--;
        }

        // 지워야 하는 문양을 +1, 나머지문양을 -1
        // ( 가 많을때 왼쪽에서 오른쪽으로 진행. 음수 나오면 x, 0이상 나오도록 진행
        if(cnt>0){
            int prev=0;
            int toBeDeleted = 0;
            if(str.charAt(0) == '(') prev++;
            else if(str.charAt(0) == ')') prev--;

            for(int i=1; i<str.length(); i++) {
                int curr = prev;
                if(str.charAt(i) == '(') {
                    curr++;
                    toBeDeleted++;
                }
                else if(str.charAt(i) == ')') curr--;

                if(prev==0 && curr==1) {
                    N -= toBeDeleted;
                    toBeDeleted = 0;
                }
                prev = curr;
            }
        }
        // ) 가 많을때 오른쪽에서 왼쪽으로 진행. 음수 나오면 x, 0이상 나오도록 진행
        else if(cnt<0){
            int prev = 0;
            int toBeDeleted = 0;
            if(str.charAt(str.length()-1) == ')') prev++;
            else if(str.charAt(str.length()-1) == '(') prev--;

//            System.out.println("prev = " + prev);

            for(int i=str.length()-2; i>=0; i--) {
                int curr = prev;
                if(str.charAt(i) == ')') {
                    curr++;
                    toBeDeleted++;
                }
                else if(str.charAt(i) == '(') curr--;

                if(prev==0 && curr==1) {
                    N -= toBeDeleted;
                    toBeDeleted = 0;
                }
                prev = curr;
            }
        }
        System.out.println(N);
        bw.flush();
        bw.close();
        br.close();
    }
}