[백준 24552] 올바른 괄호

올바른 괄호(24552)

문제 출처 : https://www.acmicpc.net/problem/24552

 

이 문제를 처음 보았을 때 스택을 이용하여 문제를 해결한다고 생각했습니다. 보통 괄호 문제는 스택에 넣어가며 문제를 해결하기가 쉽기 때문 입니다. 아직 괄호 문제를 풀어본 경험이 없다면 먼저 아래 문제부터 해결해 보시기 바랍니다.

https://davincicoding.tistory.com/189

[백준 9012] 괄호

 

위 링크를 통해 수학적으로 해결하는 방식을 이해해야 이 문제 풀이를 보다 쉽게 이해할 수 있습니다.

문제 이해하기

이 문제는 올바른 괄호가 구성되어 있는지 확인하는 문제가 아닙니다. 문제 자체에는 잘못된 괄호가 주어지고, 여기서 하나의 괄호를 빼서 올바른 괄호를 만드는 것입니다. 이 때 올바른 괄호를 만들기 위해 몇 개의 괄호 문자열을 제거할 수 있는지 경우의 수를 묻는 문제 입니다.

어느 괄호를 지워야 하는가?

( ) ( ( ) ) )

위와 같이 문제의 예제처럼 괄호가 주어졌을 때 어느 괄호를 뺄 수 있을지 생각해 보겠습니다.

( ) ( ( ) ) )

열리는 괄호는 파란색, 닫는 괄호는 빨간색 입니다. 괄호의 개수는 파란색은 3개, 빨간색은 4개 입니다. 즉 빨간 괄호를 1개 줄일 때 파란색과 빨간색의 숫자가 같아지게 됩니다. 이 예제에서는 빨간 괄호의 개수 4가 답이 됩니다.

지울 수 없는 괄호는?

하지만 이렇게 괄호의 개수로만 문제를 파악해서는 안됩니다. 왜냐하면 괄호는 열리고, 닫혀야 하는데 닫히는 괄호가 먼저 나오면 안되기 때문 입니다.

( ) ( ( )

이번에는 파란 괄호가 3개이고, 빨간 괄호가 2개 입니다. 위 예제처럼 단순히 파란 괄호의 개수가 더 많기 때문에 파란 괄호의 개수인 3이라고 답을 하면 틀리게 됩니다. 왜냐하면 첫 번째 파란색 괄호를 빼는 순간 올바른 괄호가 될 수 없기 때문 입니다.

) ( ( )

첫 번째 파란색 괄호를 빼면 위와 같은 모양이 되면서 올바른 괄호가 되지 않습니다. 괄호가 열리고 닫히는 것을 파악해서 더 이상 뺄 수 없는 괄호는 건드리지 않아야 합니다. 즉 괄호의 합계가 0이 되는 순간이 온다면 그 이전의 괄호에서는 뺄 수 있는 괄호가 없다는 뜻입니다.

합계가 0보다 작아진다면?

앞서 9012 문제에서는 괄호의 합계가 0보다 작아지면 올바른 괄호를 만들 수 없다고 바로 판단하였습니다. 하지만 이 문제에서는 그런 걱정은 할 필요가 없습니다. 왜냐하면 이 문제에서는 답이 1 이상이라고 정의를 했기 때문 입니다. 즉 합계가 0 이하라면 우리가 지워야 할 대상이라는 뜻입니다.

( ( ) ) ) ( )

위 예제에서 빨간색 괄호 3번째가 되었을 때 괄호의 합계가 0보다 작아지게 됩니다. 그럼 앞선 빨간색 괄호의 개수 3개가 답이 됩니다.

코드 작성하기

그럼 코드를 작성해보도록 하겠습니다.

입력 받고, 답 출력하기

S = input()

print(solve(S))

괄호 문자열 S를 입력 받습니다. 그리고 solve 함수를 통해 원하는 결과를 얻어 출력 합니다.

solve 함수

def solve(arr):
    left_cnt = 0
    right_cnt = 0
    total = 0

    for s in arr:
        if s == '(':
            left_cnt += 1
            total += 1
        elif s == ')':
            right_cnt += 1
            total -= 1
        
        if total < 0:
            return right_cnt
        
        if total == 0:
            left_cnt = 0

    return left_cnt

9012번과 유사합니다. 다른점은 ‘(’를 만났을 때 left_cnt를 늘려줍니다. 그리고 ‘)’를 만나면 right_cnt를 늘려줍니다.

total이 0보다 작아진다는 것은 괄호가 이미 올바르지 않다는 뜻입니다. 이 때에는 right_cnt가 답이 됩니다. 위에서 합계가 0보다 작아지는 경우가 이 경우 입니다.

total 값이 0인경우 left_cnt 값을 0으로 초기화 합니다. total이 0이되면 더 이상 그 괄호 문자열에서는 뺄 괄호가 없기 때문에 0으로 초기화를 시켜주어야 합니다.

마지막으로 left_cnt 값을 출력해주면 답이 됩니다. right_cnt값을 답으로 출력하지 않는 이유는 right_cnt 값은 total 값이 0보다 작은 경우에 이미 쓰였습니다. 최종적으로 모든 반복문을 다 돌았다면 total 값이 0보다 크다는 뜻이고, 그것은 left_cnt 값만 의미가 있다는 뜻입니다.

전체 코드

전체 코드를 알아보겠습니다.

S = input()

def solve(arr):
    left_cnt = 0
    right_cnt = 0
    total = 0

    for s in arr:
        if s == '(':
            left_cnt += 1
            total += 1
        elif s == ')':
            right_cnt += 1
            total -= 1
        
        if total < 0:
            return right_cnt
        
        if total == 0:
            left_cnt = 0

    return left_cnt

print(solve(S))