[BaekJoon] 5875 오타 (Java)

1.  문제 링크

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

2.  문제

3.  소스코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {
    static char[] brackets;

    static void input() {
        Reader scanner = new Reader();
        brackets = scanner.nextLine().toCharArray();
    }

    /*
     * 여는 괄호는 1을 더해주고, 닫는 괄호는 1을 빼주며 괄호의 상태를 누적해나간다
     *  - 최종 누적값이 -2이거나 2라면 닫는 괄호 또는 영는 괄호에 대해 1개의 오타가 존재한다는 뜻이 된다
     *  - 누적값이 -1이 되는 순간에는 닫는 괄호의 개수가 하나 더 많다는 것을 뜻이다
     *      - 이럴 때에는 그때까지의 닫는 괄호 개수가 총 변경할 수 있는 경우의 수가 된다
     *      - 닫는 괄호가 하나 더 많아지는 상태가 된다면 이후에 여는 괄호가 나와도 해당 닫는 괄호와 올바른 괄호쌍을 맞출 여는 괄호가 없으므로
     *        그때까지의 닫는 괄호 개수가 총 변경할 수 있는 경우의 수가 된다
     *
     * 그럼 총 2개의 경우를 생각해볼 수 있다
     *  1. 닫는 괄호의 개수가 더 많은 경우
     *  2. 여는 괄호의 개수가 더 많은 경우
     *
     * 1. 닫는 괄호의 개수가 더 많은 경우
     *      - 닫는 괄호가 더 많아지는 순간에서의 닫는 괄호의 개수만큼 바꿀 수 있다
     *      - 여는 괄호와 닫는 괄호가 하나의 쌍을 이루어야하므로 두 괄호의 개수가 같아야 한다
     *      - 시작 괄호는 여는 괄호, 끝나는 괄호는 닫는 괄호여야하기 때문에 닫는 괄호가 더 많아지는 순간에서의 닫는 괄호의 개수만큼 바꿀 수 있다
     * 2. 여는 괄호의 개수가 더 많은 경우
     *      - 여는 괄호의 수가 닫는 괄호의 수보다 2개 이상 많지 않으면, 그 괄호들은 바꿀 수 없다
     *          - 시작 괄호는 여는 괄호, 마지막 괄호는 닫는 괄호여야하기 때문에 그렇다!
     *      - 누적값이 1 이하일 때는 여는 괄호의 수를 계속 0으로 초기화시켜준다
     *      - 그 이후부터는 마찬가지로 여는 괄호, 닫는 괄호의 개수 및 누적값을 구해나가고
     *        두 경우에 따라 진행한다
     */
    static void solution() {
        int openBracket = 0;
        int closeBracket = 0;
        int totalBracket = 0;
        int answer = 0;

        for (int idx = 0; idx < brackets.length; idx++) {
            if (brackets[idx] == '(') {
                openBracket++;
                totalBracket++;
            } else {
                closeBracket++;
                totalBracket--;
            }

            if (totalBracket <= 1) {
                openBracket = 0;
            }
            if (totalBracket == -1) {
                answer = closeBracket;
                break;
            }
        }

        if (totalBracket > 0) {
            answer = openBracket;
        }

        System.out.println(answer);
    }

    public static void main(String[] args) {
        input();
        solution();
    }

    static class Reader {
        BufferedReader br;

        public Reader() {
            br = new BufferedReader(new InputStreamReader(System.in));
        }

        String nextLine() {
            String str = "";
            try {
                str = br.readLine();
            } catch (IOException e) {
                e.printStackTrace();
            }
            return str;
        }
    }
}