[BAEKJOON 백준] 5875 오타 (JAVA)

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

5875번: 오타

문제

올바른 괄호쌍을 좋아하는 키파는 최근에 노트북을 샀다. 그런데 키보드의 크기가 너무 작았기 때문에, 키파는 혹시 여는 괄호와 닫는 괄호를 서로 잘못 입력하지 않았는지 걱정되었다. 키파를 도와 올바른 괄호쌍이 되도록 고쳐 주자.

키파는 괄호를 입력할 때 매우 조심했기 때문에 최대 한 번 오타를 내었다. 올바른 괄호쌍은 다음과 같이 정의된다:

• ()는 올바른 괄호쌍이다.
• A가 올바른 괄호쌍이라면 (A) 또한 올바른 괄호쌍이다.
• A와 B가 올바른 괄호쌍이라면 AB 또한 올바른 괄호쌍이다.

입력

첫째 줄에 키파가 입력한 괄호열이 주어진다. 길이는 1 이상 100,000 이하이다.

출력

첫째 줄에 하나의 문자만 고쳐서 올바른 괄호쌍이 될 수 있는 경우의 수를 출력한다.

예제 입력 1 복사

()(())))

예제 출력 1 복사

4

힌트

키파가 입력한 다음 문자열을 자세히 보자:

12345678
()(())))

2번째 문자 )를 (로 고침으로써 올바른 문자열을 만들 수 있다:

12345678
(((())))

비슷하게, 5번째 문자, 6번째 문자, 혹은 7번째 문자를 고침으로써 올바른 문자열을 만들 수 있다.

'오탈자가 1개만 존재한다!' 가 이 문제의 핵심이다.

문자열에서 오탈자가 존재할 수 밖에 없는 영역이 나오면

뒤에 있는 건 고려하지 않는다. 뒤에건 오탈자가 없어야 하므로...

이 문제 자체가 '전제조건'을 '!특히!' 고려해줘야한다!!!

우선, 여는괄호 '(' = +1, 닫는괄호 ')' = -1 로 두고, 입력된 괄호문자열을 리스트로 받는다.

그 리스트를 for문으로 차례차례 돌면서 total 값도 구해준다.

이 문제의 조건은 최대 1개의 오타가 존재하는 것이므로,

최종 total 값은 ')' 가 오탈자면 -2, '('가 오탈자면 +2 만 가능하다.

그리고, for문 돌면서 total 값이 -2 아래로 내려가면 안된다.

( ) ) ) ) ( -> total : 1, 0, -1, -2, -3, -2
( ) ) ) ) ) ( ( ( -> total : 1, 0, -1, -2, -3, -4, -3, -2, -1
( ) ) ) ) ) ) ( ( ( -> total : 1, 0, -1, -2, -3, -4, -5, -4, -3, -2

위의 예시를 보면,

total 값이 -2 미만의 값을 가질 경우, 오탈자가 2개 이상이 된다.

따라서 오탈자가 '1개만' 나오는 total의 최솟값이 -2라는 것을 알 수 있다.

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

public class Main {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String str = br.readLine();
		int len = str.length();
		int left = 0;
		int right = 0;
		int total = 0;
		int result = 0;

		for (int i = 0; i < len; i++) {
			char value = str.charAt(i);
			if (value == '(') {
				left++;
				total++;
			} else {
				right++;
				total--;
			}
			if (total == 1) {
				left = 0;
			}
			if (total == -1) {
				result = right;
                break;
			}
		}
		if (total == 2) {
			result = left;
		}
		System.out.println(result);
	}
}