다른 사람 풀이
arr = list(input())
N = len(arr)
left_bracket = 0
right_bracket = 0
total_bracket = 0
result = 0
for i in range(N):
if arr[i] == '(':
left_bracket += 1
total_bracket += 1
else:
right_bracket += 1
total_bracket -= 1
if total_bracket <= 1: # 지금까지의 '('은 바꿀 수 없다
left_bracket = 0
if total_bracket == -1: # ')'이 한 개 더 많아지는 순간 지금까지의 모든 ')' 바꿀 수 있다
result = right_bracket
break # 오타는 최대 1개기 때문에 더 이상 체크는 무의미하다
if total_bracket > 0:
result = left_bracket
print(result)풀이
누적합이 음수가 되면 안된다. -1이 되는 시점에서 오타가 난 것이다. 그러면 틀린 것 포함 앞부분 닫힌 괄호의 개수가 정답이 된다.또한 끝이 양수로 나도 안된다.
누적합을 끝까지 구했을 때 마지막이 +2 또는 -2일 때, 한 개가 오타난 경우다
왼쪽 괄호가 더 많은 경우에는, 케이스 분리를 해야하는데 왼쪽 괄호가 바뀔 수 없는 경우가 있다. 만약 여는 괄호의 수가 닫는 괄호의 수보다 2개이상 많지 않다면 그 괄호를 바꿀 수 없는데 최외각의 괄호에서 열고 시작했을 수 있기 때문이다.
따라서 전체 괄호 개수가 1개 이하일 때는 왼쪽 괄호 수를 0으로 계속 초기화시켜주고, 그 이후부터 잉여 왼쪽 괄호의 개수를 세주면 된다.
예시
()()()
( ) ( ) ( (
1 0 1 0 1 2
답:1
( ) ( ) ) )
1 0 1 0 -1 -2
답:3
( ) ( ( ( )
1 0 1 2 3 2
답:2
( ) ) ) ( )
1 0 -1 -2 -1 -2
답:2
( ( ( ) ( )
1 2 3 2 3 2
답:3
) ) ( ) ( )
-1 -2 -1 -2 -1 -2
답:1
((()))
( ( ( ) ) (
1 2 3 2 1 2
답:1
( ( ( ) ( )
1 2 3 2 3 2
답:3
( ( ( ( ) )
1 2 3 4 3 2
답:3
( ( ) ) ) )
1 2 1 0 -1 -2
답:3
( ) ( ) ) )
1 0 1 0 -1 -2
답:3
) ( ( ) ) )
-1 0 1 0 -1 -2
답:1
( ) ) ( ) )
1 0 -1 0 -1 -2
답:2