[BOJ/백준] 5875 오타

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


if total_bracket > 0:
    result = left_bracket

print(result)

 

 

이 문제는 어려웠던 문제였다. 이 문제는 괄호의 특성을 이해하고, 그것의 패턴을 찾아서 생각을 해줘야했던 문제였다.

 

이 문제의 조건은 최대 1개의 오타가 존재할 수 있다.

 

여는 괄호를 +1, 닫는 괄호를 -1로 할씨, 마지막의 최종 괄호의 수가 -2 이거나 2이면 1개의 오타가 존재하는 것이고,

 

-1이 되는 순간 닫는괄호가 1개가 더 많은 것을 확인할수 있는 순간이다.

 

이 문제에서 닫는괄호의 갯수가 더 많을 경우에는 닫는 괄호가 더 많아지는 그 순간에서의 닫는 괄호의 갯수만큼을 바꿀수 있다.

 

그리고, 이 문제에서 어려웠던 것은 왼쪽괄호가 더 많을 경우이다. 왼쪽 괄호가 더 많은 경우에는 왼쪽괄호가 절대 바뀔수 없는 경우들을 생각을 해줘야한다.

 

만약 여는 괄호의 수가 닫는괄호의 수보다 2개이상 많지 않으면, 그 괄호들은 바꿀수가 없다. 이 문제에서 최외각의 괄호들은 왼쪽은 여는괄호 오른쪽은 닫는괄호 인 것을 상기해보면 풀 수 있다.

 

이러한 점을 응용해, 전체 브라켓의 갯수가 1개 이하일때에는 왼쪽 괄호의 수를 계속 0으로 초기화를 시켜주는 작업을 하고, 그 이후부터 잉여 왼쪽 브라켓의 개수를 세주는 작업을 하는 방식으로 풀 수 있다.

 

 

# 	babygranfa 코드 분석
arr = list(input())
N = len(arr)
left_bracket = 0
right_bracket = 0
total_sum = 0
left_stack = []
right_stack = []
left_list = [0]*N
right_list = [0]*N

for i in range(N):
    if arr[i] == '(':
        left_bracket += 1
        total_sum += 1
        left_stack.append(i)
    else:
        right_bracket += 1
        total_sum -= 1
        if left_stack:
            left_stack.pop()
        else:
            right_stack.append(i)
    
    left_list[i] = left_bracket
    right_list[i] = right_bracket

if total_sum > 0:
    print(left_list[-1] - left_list[left_stack[-1]]+1)
elif total_sum <0:
    print(right_list[right_stack[0]])
else:
    print(0)

이 방식은 다른사람의 풀이를 보고 습득한 방법이다.

 

이 풀이는 자료구조를 이용해서, 여는 괄호의 위치를 저장해주는 스택과 닫는 괄호를 저장해주는 스택을 해준다.

 

여기서 쌍을 이루는 스택들은 하나씩 제거를 해주면서, 여는 괄호가 없고, 닫는괄호가 있을때에는 그때의 위치를 저장시켜준다.

 

이런식으로 하면서, 전체 브라켓의 개수가 양수일때에는 왼쪽괄호가 더 많은 것이므로, 왼쪽괄호의 최종 개수에서 마지막 왼쪽괄호의 스택이 위치가 존재하는 곳의 왼쪽괄호의 개수를 빼주고 1개를 더해준다. 그 위치의 왼쪽괄호도 포함되어야하기 때문이다.

 

그리고 오른쪽괄호같은경우엔, 최초로 오른쪽괄호가 많아지는 곳의 오른쪽괄호의 수를 출력해주면 된다.

 

 

이 문제는 괄호의 특성을 이해하고, 그것을 적용시키는 문제로, 저에게 상당히 어려웠던 문제였다.