[백준 9012] 괄호

괄호(9012)

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

 

이 문제는 다빈치코딩 알고리즘에서 이미 스택으로 풀어본 문제 입니다. 이전 스택 풀이는 아래 링크를 확인 바랍니다.

https://wikidocs.net/215110

06. 괄호[백준 9012]

 

그럼에도 다시 이 문제를 풀이하는 이유는 스택 말고도 다른 풀이 방법이 여러가지가 있기 때문 입니다. 괄호를 사용한 문제는 여러가지가 있기 때문에 다른 풀이 방법도 익숙해져야 그 문제에 맞는 풀이법을 사용할 수 있기 때문 입니다.

스택을 이용한 방법 외에 크게 두 가지 방법이 있습니다. 문자열을 이용하는 방법과 수학적으로 해결하는 방식입니다.

문자열 풀이 방법

먼저 문자열을 사용한 풀이 방법 입니다. 이 방법은 괄호쌍을 찾아 지워나가는 방법 입니다. 제대로 되어 있는 괄호쌍을 지워나가다 보면 남는 문자열이 하나도 남아있지 않게 됩니다. 만약 하나라도 남은 괄호가 있다면 그것은 올바른 괄호가 아닌 것입니다.

T = int(input())

for _ in range(T):
    ps = input()

    while "()" in ps:
        ps = ps.replace("()", "")
    
    if ps:
        print("NO")
    else:
        print("YES")

괄호 문자열 ps를 입력 받습니다. 그리고 ps 에 있는 괄호쌍 “()” 이 보이면 하나씩 지워나갑니다.

replace는 “바꾸다” 라는 뜻을 가지고 있습니다. 즉 주어진 문자열에서 첫 번째 매게변수와 같은 문자열을 찾으면 해당 문자열을 두 번째 매게변수로 바꿔주라는 뜻입니다. 즉 위 함수는 주어진 문자열 ps에서 괄호쌍을 찾아 모두 지워주라는 뜻입니다.

while 반복문이 모두 수행 완료 되었을 때 하나라도 남은 괄호가 있다면 그것은 올바른 괄호 문자열이 아닙니다. ps에 남은 괄호가 있다면 NO를, 남은 괄호가 더이상 없다면 YES를 출력합니다.

수학적 풀이법

수학적으로 풀이하는 방식은 괄호의 개수를 더하거나 빼면서 올바른 괄호 문자열인지 파악하는 방법 입니다. 괄호가 열릴 때 즉 “(” 문자를 만날 때 숫자를 1 더해주고, 괄호가 닫힐 때 즉 “)”를 만났을 때 숫자를 1 빼줍니다. 모든 문자열 탐색을 끝냈을 때 숫자가 0이면 올바른 괄호 문자열 입니다. 만약 숫자가 0이 아니라면 괄호쌍이 맞지 않기 때문에 올바른 괄호 문자열이 아닙니다.

단순히 숫자가 0인지 아닌지로만 파악하면 안됩니다.

)(

위와 같이 열리는 괄호와 닫히는 괄호의 개수가 같더라도 올바른 괄호가 되지 않을 수 있기 때문 입니다. 괄호는 열린 다음 닫혀야 합니다. 즉 괄호의 개수를 계산할 때 0보다 작아지는 순가이 온다면 닫히는 괄호가 더 많다는 뜻이고, 이것은 올바른 괄호가 아니라는 뜻입니다.

T = int(input())

def solve(ps):
    total = 0
    for p in ps:
        if p == "(":
            total += 1
        else:
            total -= 1
        
        if total < 0:
            print("NO")
            return
    
    if total:
        print("NO")
    else:
        print("YES")
    return

for _ in range(T):
    ps = input()
    solve(ps)

문자열 ps를 입력 받아 탐색을 합니다. “(”를 만나면 total 값을 1 더해주고, “)”를 만나면 total 값을 1 빼줍니다. 만약 total 값이 0보다 작아진다면 닫히는 괄호가 열리는 괄호보다 더 많다는 뜻이고, 이런 경우는 올바른 괄호가 될 수 없어 바로 NO를 출력하고 빠져나옵니다.

모든 탐색을 끝내고 total 값이 0이 아니라면 올바른 괄호가 아니기 때문에 NO를 출력합니다. total 값이 0이라면 모든 괄호가 올바르게 되어 있는 것이기 때문에 YES를 출력하고 종료합니다.

마치며

괄호의 다양한 풀이 방법을 알아보았습니다. 스택, 문자열, 수학 등등 이것 말고도 더 많은 풀이 방법이 있을 수 있습니다. 괄호를 사용하는 다양한 문제가 있기 때문에 자신이 풀어야 하는 문제에 맞게 다양한 방식으로 시도해 보시기 바랍니다.