[백준] 4949 균형잡힌 세상

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

---

문제요약

스택을 활용한 괄호 확인하기 문제

풀이

우선 문장이 주어지므로 문장에서 괄호만 리스트로 빼내야 된다.

parentheses = ['(', ')']
square_brackets = ['[', ']']

while True:
    sentence = input()
    if sentence == '.': break

    brackets_list = []
    for text in sentence:
        if text in parentheses or text in square_brackets:
            brackets_list.append(text)

반복문을 돌면서 독점(.)이 나올때까지 문장을 입력받는다. 괄호는 리스트로 미리 정의해 두었다. text가 괄호에 포함된다면 괄호리스트(brackets_list)에 추가해 준다.

---

 

# 괄호가 완전한 괄호이면 True반환
def check_brackets(top, bracket):
    # top이 열린 괄호고 bracket이 닫힌 괄호일 경우
    if (top == parentheses[0] and bracket == parentheses[1]) or (top == square_brackets[0] and bracket == square_brackets[1]):
        return True
    else:
        return False

괄호가 완전한 괄호인지 확인하는 함수이다. 스택의 top과 괄호 리스트의 가장 앞의 요소를 비교하여 완전한 괄호이면 True 를 아니면 False 를 반환한다.

---

def check_sentence(brackets_list):
    if not brackets_list:
        return True

    stack = []
    stack.append(brackets_list.pop(0))

    while brackets_list:
        # 스택이 비어 있다면 bracket_list에서 pop하여 추가
        if not stack:
            stack.append(brackets_list.pop(0))
        if not brackets_list:
            break
        top = stack[-1]

        if check_brackets(top, brackets_list[0]):
            stack.pop()
            brackets_list.pop(0)
        else:
            stack.append(brackets_list.pop(0))

    if stack:
        return False

    return True

스택을 이용하여 괄호를 체크하는 함수이다. 스택에 괄호리스트의 요소를 하나씩 추가해주고 괄호리스트는 앞에서부터 차례로 pop한다. 여기서 IndexError 가 발생하지 않도록 주의해주어야 된다. 괄호리스트 혹은 스택이 빈 배열인데 pop을 수행할 경우 IndexError 가 발생한다.

괄호리스트가 모두 스택으로 옮겨졌는데도 스택에 남아있는 요소가 있을 경우 괄호는 완전하지 않은 괄호이다.

---

소스코드는 Python 3으로 작성되었습니다.

parentheses = ['(', ')']
square_brackets = ['[', ']']


# 괄호가 완전한 괄호이면 True반환
def check_brackets(top, bracket):
    # top이 열린 괄호고 bracket이 닫힌 괄호일 경우
    if (top == parentheses[0] and bracket == parentheses[1]) or (top == square_brackets[0] and bracket == square_brackets[1]):
        return True
    else:
        return False



def check_sentence(brackets_list):
    if not brackets_list:
        return True

    stack = []
    stack.append(brackets_list.pop(0))

    while brackets_list:
        # 스택이 비어 있다면 bracket_list에서 pop하여 추가
        if not stack:
            stack.append(brackets_list.pop(0))
        if not brackets_list:
            break
        top = stack[-1]

        if check_brackets(top, brackets_list[0]):
            stack.pop()
            brackets_list.pop(0)
        else:
            stack.append(brackets_list.pop(0))

    if stack:
        return False

    return True


while True:
    sentence = input()
    if sentence == '.': break

    brackets_list = []
    for text in sentence:
        if text in parentheses or text in square_brackets:
            brackets_list.append(text)
    if check_sentence(brackets_list):
        print('yes')
    else:
        print('no')