[백준 온라인 저지] 균형잡힌 세상

문제 출처

• https://www.acmicpc.net/problem/4949

4949번: 균형잡힌 세상

 

문제 해설

• 문자열에 포함된 괄호의 열고 닫음이 짝이 잘 이루어져 균형이 잘 이루어져 있는지 확인하는 문제
• 문제에서 사용된 괄호는 소괄호("()"), 대괄호("[]")
• 균형이 잘 이뤄어져 있는지 판단하는 조건
  
  • 모든 여는 소괄호("(")는 닫는 소괄호(")")와만 짝을 이룬다.
  • 모든 여는 중괄호("[")는 닫는 중괄호("]")와만 짝을 이룬다.
  • 모든 닫는 괄호는 짝을 이루는 여는 괄호가 존재
  • 여는 괄호와 닫는 괄호는 1대1로 매칭
• "." 마침표가 입력되면 프로그램 종료

 

문제 풀이

# source: https://www.acmicpc.net/problem/4949

while True:
    line = input()

    if line == ".":
        break

    result = True
    stack = []
    for c in line:
        if c == "(" or c == "[":
            stack.append(c)
        elif c == ")" or c == "]":
            if len(stack) == 0:
                result = False
                break
            data = stack.pop(-1)
            if c == ")" and data != "(":
                result = False
                break
            elif c == "]" and data != "[":
                result = False
                break
    if len(stack) != 0:
        result = False

    print("yes" if result else "no")

• 문자열의 문자를 하나씩 읽으면서 여는 괄호인 나오는 경우에는 스택에 저장하고 닫는 괄호가 나오는 경우에는 스택의 마지막 부분과 비교하여 짝을 이루는지 확인
• 짝을 이루지 않는다면 균형이 맞지 않는 것으로 판단하여 반복 종료
• 마지막으로, 스택이 비어있지 않는 경우에는 짝을 이루지 못한 여는 괄호가 존재하는 것이므로 균형이 맞지 않는 것으로 판단

 

Github

• https://github.com/limseunghyun95/Algorithm_study/blob/master/baekjoon/p_4949.py