백준) 괄호

토요일 새벽에 문제를 풀어서 강의를 적용하지 않은 방식과 적용한 방식 2가지를 소개하겠다.

 

 

간단하게 요약하자면 괄호가 제대로 닫히는지 확인하는 로직을 짜라는 문제다.

그리고 그것을 VPS라고 부른다.

 

이 문제를 보고 처음에 든 생각은 '입력 값은 무조건 짝수여야만 하겠구나'였다.

하지만 올바르지 않은 VPS도 짝수개 일 수 있다.

 

예제를 보며 10분간 멍때리다 보니 답이 생각났다.

왼쪽 괄호(Opener)와 오른쪽 괄호(Closer)의 갯수를 카운트하면 답이 나온다

Closer의 수 가 Opener 의 수보다 많아 질때 VPS가 되지 못 한다. (왼쪽부터 계산했을 때)

( ) ) ( ( ) 

 

이 시점에서 뒤에있는 문자열은 체크할 필요없이 "NO"를 출력하면 된다.

만약에 끝까지 오른쪽 괄호가 왼쪽 괄호보다 많아지지 않았다면 두 괄호의 숫자가 같은지 확인 한 후 같다면 "YES"를 출력하면 된다.

 

import sys
inputs_len = int(input())
inputs = [sys.stdin.readline()[:-1] for _ in range(inputs_len)] # 백준의 아주 어려운 입력방식

for i in range(int(inputs_len)):
    flag = 0  # 괄호갯수 차이로 반복문이 깨졌는지 확인하는 변수
    input_word = list(inputs[i]) # pop함수를 쓰기 위해 문자열을 list로 변환함
    left = 0
    right = 0
    while input_word:      # 더이상 pop할수 없을 때 까지 반복(문자열이 비어있을 때 까지)
        if input_word.pop() == ")":    # opener closer 카운트
            right += 1
        else:  # elif t1 == "(":
            left += 1

        if right < left:            # opener가 closer 보다 많다면 반복문 탈출
            flag = 1
            break
    if flag == 0 and right == left:  # 반복문이 깨졌는지, 괄호의 갯수가 같은지 확인
        print("YES")
    else:
        print("NO")

 

elif 대신 else문을 사용해 코드를 한 줄 줄이고 공간도 줄이고 계산도 한 번 덜 하게 만들었다.

 

 

 

 

오늘 배웠던 스택만을 활용해 푸는 로직도 짜봤다.

opener와 closer를 하나씩 매칭시키는 방식으로 스택이 비었을 때 closer가 나오면 오답 처리를 한다.

import sys
inputs_len = int(input())
inputs = [sys.stdin.readline()[:-1] for _ in range(inputs_len)] # 백준의 아주 어려운 입력방식

for i in range(int(inputs_len)):
    stack = []
    flag = 0

    for j in inputs[i]:
        if j == "(":    # opener가 맞다면 stack에 추가
            stack.append(j)
        else:   # opener가 아니라면
            if not stack:   # 스택이 비었다면 반복문 탈출
                flag = 1
                break

            stack.pop()    # opener 하나 삭제

    if flag == 0 and not stack:  # 반복문이 깨졌는지, 스택이 비었는지 확인
        print("YES")
    else:
        print("NO")