[백준] 5875 오타 python(파이썬)

풀이 및 사고

일단 누적합이라는 걸 알고 풀긴했다.. ㅎ

문제에서 최대 한번의 오타를 냈다는 말이 있다. 이 말로 케이스(나올 수 있는 누적합 경우의 수)가 확 줄어들기 때문에 꼭 기억하고 풀어야 한다.

처음 생각으로는 여는 괄호를 1, 닫는 괄호를 -1로 체크한 배열을 만들었다. 예시는 닫는 괄호가 더 많은 케이스라 누적합 처리를 하면 배열의 총합이 -2가 나온다.

()(()))) ⇒ [1, -1, 1, 1, -1, -1, -1, -1] ⇒ [1, 0, 1, 2, 1, 0, -1, -2]

여기서 문제가 어떤 괄호를 고쳐야 올바른 괄호쌍이 될 수 있는지 판단해야 하는 것이다.

나올 수 있는 케이스를 먼저 생각해보면 누적합이 0, 2, -2인 케이스 밖에 없다.

올바른 괄호쌍이거나 여는 괄호가 1개 많은 경우이거나 닫는 괄호가 1개 많은 경우인 것이다.

주어진 예시로 만든 누적합 배열에서 -1이 되는 순간 닫는 괄호의 개수가 많아진다. 그래서 -1까지의 닫는 괄호 중에 하나를 골라서 바꿔줘야한다. -1 이후의 괄호를 바꾸는 것은 의미가 없는 이유가, 이미 앞의 괄호쌍이 올바르지 않기 때문이다. 이 경우는 누적합이 -2인 경우이다

문제는 누적합이 2인 경우인데, 복잡하게 생각하지 말고 위의 경우를 반대로 생각하면 된다. 뒤에서부터 누적합 배열을 만드는 것이다. 뒤에서부터 생각하면 기존의 열린 괄호를 닫힌 괄호로 인식하고 문제를 풀면 된다. 예시를 들어보면 (()(() ⇒ [1, 1, -1, 1, 1, -1] ⇒ (순서는 적기 쉽게 거꾸로 바꿨다) [-1, 0, 1, 0, 1, 2] 이 된다. 여기서 1이 되는 순간 열린 괄호(뒤에서 보면 닫힌 괄호)의 개수가 더 많아지는 곳이다. 그래서 이 부분까지(뒤에서 센다)의 열린 괄호를 바꾸면 올바른 괄호쌍을 만들 수 있다. 누적합이 -2(닫힌 괄호가 더 많음)인 경우와 마찬가지로 1이 되는 부분 이후의 열린 괄호를 바꿔 봤자 소용이 없다. 이미 (누적합 배열 기준, 기존 괄호 기준 뒷 부분) 앞 부분의 괄호쌍이 올바르지 않으므로.

코드

import sys
read = sys.stdin.readline

s = read().rstrip()
arr = [0] * len(s)
for i in range(len(s)):
    if s[i] == '(':
        arr[i] = 1
    else:
        arr[i] = -1
hap = sum(arr)
cnt = 0
imos = []
if hap == -2: # 닫는 괄호가 하나 더 많음
    imos.append(arr[0])
    for i in range(1, len(arr)):
        imos.append(imos[i-1]+arr[i])
        if arr[i] == -1:
            cnt += 1
        if imos[i] == -1: # 닫는 괄호가 더 많아지는 부분
            break
elif hap == 2: # 여는 괄호가 하나 더 많음
    imos.append(arr[-1])
    for i in range(1, len(arr)):
        imos.append(imos[i-1]+arr[-1-i]) # arr 거꾸로 누적합
        if arr[-1-i] == 1:
            cnt += 1
        if imos[i] == 1: # 여는 괄호가 많아지는 부분(뒤에서 출발하는 시점에서 보면 닫는 괄호가 많아지는 부분)
            break
print(cnt)