[백준] 오타 - 5875

문제링크

5875번: 오타

 

최대 100,000개의 입력값이 주어지며 1초의 시간 안에 풀어야 하므로 log(n) ~ nlog(n) 안에 풀어야 합니다.

 

변경할 괄호의 위치를 순환하는 n은 필수적으로 소모되므로

변경된 문자열이 올바른 괄호쌍인지 판단하는데 소모되는 시간은 log(n) 보다 짧아야 합니다.

 

문제를 풀기 위해 누적합(prefix sum) 알고리즘을 사용했습니다.

해당 알고리즘은 n만큼의 시간을 소요하여 새로운 정보를 만든 후 해당 정보를 1만큼의 시간을 통해 가공하여 답을 찾습니다.

풀이

여는 괄호 '('는 1, 닫는 괄호 ')'는 -1 값으로 설정한 후 순차적으로 값을 더하는 방식으로 누적합 배열을 만듭니다.

문자열이 올바른 괄호쌍일 경우 누적합 배열의 최종 값은 0이 되어야 합니다. (각 괄호의 숫자가 동일하므로)

 

하지만 주어진 문제의 경우 최대 한 개의 문자열이 잘못되었으므로 누적합 배열의 최종값은 -2, 0, 2 세 개 중 한 개가 됩니다.

 

여기서 한 가지를 더 고려할 점이 있습니다.

))(( 문자열과 같이 각 괄호의 숫자는 동일하나 올바르지 않은 경우입니다.

이러한 문자열은 현재 위치에서 닫는 괄호의 누적 개수보가 여는 괄호의 누적 개수보다 많을 경우에 발생합니다.

즉 누적 합 배열 내에서 음수가 존재하는 경우 올바르지 않은 괄호 문자열이 됩니다.

 

다시 정리하면 올바른 문자열의 누적합은 아래 두 가지를 만족합니다.

1. 누적합 배열의 마지막 값은 0

2. 누적합 배열에 음수가 존재하지 않음

 

따라서 문자열의 앞부터 순차적으로 괄호를 변경한 후의 누적합의 상태가 위 두 가지를 만족하는지 확인하는 것으로 답을 찾을 수 있습니다.

하지만 변경된 문자열의 누적합을 구하는 기 위해서는 n의 시간이 소요되므로 더 빠른 방법을 사용해야만 합니다.

 

이를 위해 문자열을 변경하면 누적합이 어떻게 변화하는지 분석해 볼 필요가 있습니다.

아래 표는 문자열을 변경했을 때 누적합을 보여줍니다.

문자열	(	(	)	(
변경 없음	1	2	1	2
0번 변경	-1	0	-1	0
1번 변경	1	0	-1	0
2번 변경	1	2	3	4
3번 변경	1	2	1	0

 

위 표를 통해 우리는 아래 2가지의 사실을 알 수 있습니다.

1. 여는 괄호를 닫는 괄호로 수정할 경우 해당 누적합의 값부터 -2가 더해집니다.

2. 닫는 괄호를 여는 괄호로 수정할 경우 해당 누적합의 값부터 2가 더해집니다.

 

좀 더 풀어서 설명하자면

여는 괄호인 0번 문자열을 닫는 괄호로 수정하는 경우

누적합의 0번째 값부터 마지막 값까지 전부 -2가 더해진 것을 볼 수 있으며

닫는 괄호인 2번 문자열을 여는 괄호로 수정하는 경우

누적합의 2번째 값부터 마지막 값까지 전부 2가 더해지는 것을 볼 수 있습니다.

이러한 규칙은 1과 -1 사이의 차이가 2이기 때문에 발생합니다.

 

이제 규칙을 찾았으므로 이를 올바른 문자열의 누적합 규칙과 함께 살펴보겠습니다.

1. 누적합 배열의 마지막 값은 0
2. 누적합 배열에 음수가 존재하지 않음

 

우리는 최대 한 개의 괄호만 수정하기 때문에 변경될 수 있는 값은 2와 -2가 전부입니다.

 

따라서 1번 규칙을 만족시키기 위해서

마지막 값이 -2일 경우 닫는 괄호를 여는 괄호로

마지막 값이 2일 경우 여는 괄호를 닫는 괄호로

수정해야 한다는 사실을 알 수 있습니다.

 

이제 2번 규칙을 만족하기 위한 조건을 닫는 괄호를 여는 괄호로, 여는 괄호를 닫는 괄호로 바꾸는 경우로 나누어 생각해 보겠습니다.

 

여는 괄호를 닫는 괄호로 수정

변경하고자 하는 괄호의 위치를 포함해서 마지막 위치까지 전부 -2가 더해지므로

적용되는 값이 모두 2보다 크다면 2번 규칙을 만족할 수 있습니다.

 

다시 말해 누적합 내에서 2보다 큰 값으로만 이루어져 있는 인덱스를 찾은 후 해당 위치부터 존재하는 여는 괄호를 찾으면 된다.

 

닫는 괄호를 여는 괄호로 수정

변경하고자 하는 괄호의 위치부터 마지막까지 전부 2가 더해지므로

괄호의 위치보다 전에 있는 누적합에 음수가 존재한다면 2번 규칙을 만족할 수 없습니다.

 

따라서 처음부터 누적합에서 가장 처음 음수가 나온 위치를 포함한 문자열 내에 존재하는 닫는 괄호를 찾으면 됩니다.

 

풀이 코드

function solution(sequence) {
  const { length } = sequence;
  const charValue = { "(": 1, ")": -1 };
  let prefixSumArr = [];
  prefixSumArr[0] = charValue[sequence[0]];
  // 여는 괄호를 닫는 괄호로 바꿀수 있는 위치를 찾기 위한 인덱스
  let overTwoIndex = null;
  // 닫는 괄호를 여는 괄호로 바꿀수 있는 위치를 찾기 위한 인덱스
  let firstNegativeIndex = prefixSumArr[0] < 0 ? 0 : null;
  for (let i = 1; i < sequence.length; i++) {
    prefixSumArr[i] = prefixSumArr[i - 1] + charValue[sequence[i]];
    if (overTwoIndex === null && prefixSumArr[i] >= 2) {
      overTwoIndex = i;
    }
    if (prefixSumArr[i] < 2) {
      overTwoIndex = null;
    }
    if (firstNegativeIndex === null && prefixSumArr[i] < 0) {
      firstNegativeIndex = i;
    }
  }
  const totalSum = prefixSumArr[length - 1];
  if (totalSum === 2) {
    return sequence
      .slice(overTwoIndex)
      .split("")
      .filter((v) => v === "(").length;
  }
  if (totalSum === -2) {
    return sequence
      .slice(0, firstNegativeIndex + 1)
      .split("")
      .filter((v) => v === ")").length;
  }
  return 0;
}