[백준 / BOJ] 5875 오타

문제

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

5875번: 오타

오타가 '최대 한번' 있는 괄호배열이 주어진다. 

이 괄호배열의 괄호를 하나 조작하여 올바른 괄호 배열을 만드는 경우의 수 를 구하는 문제다.

---

풀이

어려웠던 문제다

누적합으로 풀었는데, 여는 괄호를 +1, 닫는괄호를 -1 이라고 하고 누적합 배열을 만들자.

예를들어, 괄호배열 ( ) 의 누적합배열은 {1, 0},  ( ( ) ) 의 누적합 배열은 {1, 2 ,1, 0}이 된다.

올바른 괄호배열이 여는괄호 '(' 가 있다면 이에 매칭되는 닫는괄호 ')'가 반드시 존재해야 한다는 것을 생각하면, 누적합 배열은 항상 0으로 끝나야하며, 어느 지점에서든지 음수가 나온다면, 여는괄호 보다 닫는괄호가 더 많은것을 의미하므로 누적합 배열에서 음수가 나오면 안된다는 것을 알 수 있다. 

 

따라서, 이 문제는 다음과 같은 조건을 만족하는지 확인하며 O(N)만에 풀 수 있다.

1) 괄호배열의 어떤 지점을 수정했을때, 누적합 배열의 마지막이 0으로 끝나는가.

2) 괄호배열의 어떤 지점을 수정했을때, 누적합 배열에 음수가 존재하지 않는가.

1,2번을 만족한다면 수정된 괄호배열은 올바른 괄호배열이다.

위 과정을 괄호배열의 모든 지점마다 반복하면 된다.

 

이때, 1번 조건은 마지막지점에 +2 혹은 -2를 해가며 O(1)만에 구할 수 있지만 2번조건을 O(1)만에 구하는게 까다로웠다.

2번조건은 다시 두개의 조건으로 나뉜다.

1) 현재 수정하는 괄호가 닫는괄호 일때

-> 현재 수정하는 괄호가 닫는괄호라면, 누적합 배열의 이전 idx에서 음수가 있는지 확인한다. 음수가 존재한다면, 이 배열은 올바른 괄호배열이 될 수 없는데, 현재 위치의 닫는 괄호를 여는괄호로 수정하고 누적합 배열의 각 idx에 +2를 해줘도 이전 위치에는 영향을 미치지 않기 때문이다.

 

2) 현재 수정하는 괄호가 여는괄호 일때

-> 현재 위치의 여는괄호를 닫는괄호로 수정했을때, 누적합 배열의 이후 idx가 음수가 되는지 확인한다. 닫는괄호로 수정하면 누적합 배열의 각 idx에 -2를 해주므로, 누적합배열의 1과 0갯수를 누적합으로 만들어 체크해줌으로 O(1)에 구할 수 있다.

위 조건대로 코드를 만들면 답이 나온다.

(설명이 이해가 안되면 코드를 보도록 하자)

 

주요 소스코드

	private int countBracketsFixablePointCount(String brackets){
		int[] bracketSum = this.sumBrackets(brackets);
		int leftMinusIdx = this.getLeftMinusIdx(bracketSum);
		int[] leftPlusArray = this.getLeftPlusArray(bracketSum);
		int fixablePoint = 0;
		boolean fixed = false;
		for(int i = 0; i < brackets.length(); i++){
			fixed = false;
			int lastPoint = bracketSum[bracketSum.length-1];
			if(this.isCloseBracket(brackets.charAt(i)) && i < brackets.length()-1 && i <= leftMinusIdx) {
				fixed = true;
				lastPoint += 2;
			}
			else if(this.isOpenBracket(brackets.charAt(i)) && i > 0 && leftPlusArray[i] == 0){
				fixed = true;
				lastPoint -= 2;
			}
			if(lastPoint == 0 && fixed) fixablePoint++;
		}
		return fixablePoint;
	}

---

전체소스코드

https://github.com/devxb/JJUNalgo/blob/master/5875%20%EC%98%A4%ED%83%80/Main.java

GitHub - devxb/JJUNalgo: 백준 알고리즘 소스코드🙃