지금까지 풀었던 문제 중에서 가장 오래 걸리지 않았나... 뭔가 머리로 로직은 있는데 이걸 제대로 풀어내지 못하고... 계속 터미널이랑 충돌하고 해서 난리부르스 ^^...

9012: 괄호

1. 첫 번째 풀이: 실패

복잡하게 생각하지 말고 단순하게 가자! 는 호기 때문에... 장렬히 실패를 맛봤다. 근데 뭐 장렬히가 아니라 그냥 당연한 거임...

import sys

N = int(sys.stdin.readline())
right = '('
left = ')'
for _ in range(N):
    input = sys.stdin.readline().strip()
    right_cnt = input.count(right)
    left_cnt = input.count(left)
    if right_cnt != left_cnt:
        print('NO')
    else:
        print('YES')

풀이를 살펴보면 right와 left 괄호의 갯수를 세어서 같으면 YES ~ 다르면 NO ~
정~말 단순하고도 바보 같은 생각이었다. 나는 약간 이런 문제 풀 때 반례를 제대로 생각하지 못하는 게 큰 문제인 듯하다. 이 풀이의 반례는

) (

이다. 네... 바보 인정합니다... 그래서 이렇게 풀지 말고 다르게 풀어야겠다고 생각해서 다양한 방법으로 접근해보았다.

2. 두 번째 풀이: 성공

정~말 다양한 방법으로 접근했는데 계속해서 YES가 떠야할 곳에 NO가... NO가 떠야할 곳에 YES가 떴다... ^^
그래도 작정하고 끝까지 푼 덕분에 영광의 '맞았습니다' 를 받아냈다! 하 뿌듯해 ;;;

import sys

N = int(sys.stdin.readline())
right = 0
left = 0
result = ''
for _ in range(N):
    input = list(sys.stdin.readline().strip())
    for i in range(len(input)):
        if input[i] == '(':
            right += 1
        else:
            left += 1
        if left > right:
            result = 'NO'
    if (result == ''):
        if (left == right):
            result = 'YES'
        else:
            result = 'NO'
    right, left = 0, 0
    print(result)
    result = ''

사실 중간에 주석이 하나 있었다. 바로 생각하다 포기한 일부...

for i in range(1,len(input)):
        if (input[i-1]==right) and (input[i]==left):
           input[i-1], input[i] = 'True', 'True'

이 풀이를 생각하게 된 건, ()의 VPS를 마주하게 되면 이를 리스트에서 빼버리는 것이었다. 이 과정을 반복하면 (()())에서 멀리 떨어진 ()도 만나게 될 것이므로 이렇게 풀면 백퍼 된다!!! 라는 생각이 머리를 지배했다. 그런데 이 풀이의 문제점은 for문의 range가 미리 정해지게 되어서 결국 index error가 난다는 것이었다. index error... 지긋지긋해... 그래서 이 방법 말고 새로운 방법으로 접근해야겠다라는 생각이 들었고, 그 결과가 바로 성공한 풀이!

성공한 풀이를 떠올리게 된 포인트는,

무슨 일이 있어도 ' ) '가 먼저 나오면 안된다!

라는 것이었다. 닫는 괄호가 먼저 나오게 되면, 무슨 짓을 해도 VPS가 될 수 없기 때문에... 이걸 지금에서야 알다니!

그래서 로직을 설명해보면,

1. 각각 괄호를 세주는 left와 right 변수를 0으로 초기화 해준다.
2. right과 left를 각각 세주고, 만약 left가 right보다 커진다!!! 하면 바로 result에 NO를 추가하도록 한다.
3. 만약 다 돌았는데, result가 여전히 빈 문자열이다? 이 말은 right가 더 크거나 둘이 같다는 말이다.
4. 그러면 둘이 개수가 같으면 VPS일 거고,
5. 다르면 VPS가 아닐 것이다.
6. 마지막으로 저장된 result 값을 출력한다!

추가로 만약 result가 빈 문자열인지 검사하는 부분이 없다면, 총 left와 right으로만 VPS를 따질 것이다. 즉 이 문자열이 '(())'이어도 '))(('이어도 똑같은 left와 right을 가지니 YES를 출력하게 되는 것이다. 결국 첫 번째 풀이와 다를 게 없다는 것... 그래서 NO라는 문자열이 지금 result에 할당되었는지 아닌지 확인이 필요한 것이다.

여기까지가 나의 풀이에 대한 설명이고, 이제 다른 풀이를 살펴보자!

3. 다른 풀이

a = int(input())
for i in range(a):
    b = input()
    s = list(b)
    sum = 0
    for i in s:
        if i == '(':
            sum += 1
        elif i == ')':
            sum -= 1
        if sum < 0:
            print('NO')
            break
    if sum > 0:
        print('NO')
    elif sum == 0:
        print('YES')

(출처: https://pacific-ocean.tistory.com/70)

백준 파이썬 풀이로 유명하신 깨지고 부서져라님... 정말 똑똑하시다. 이걸 수학적으로 접근할 생각을 하다니... 우와라는 감탄 밖에 나오지 않군... 역시 더 발전해야겠어...

오늘도 신기한 알고리즘의 세계 끝!