[BOJ] 4949. 균형잡힌 세상

📌 문제 제목

문제 링크: BOJ 4949

---

🗒️ 문제 설명

어떤 문자열이 주어졌을 때, 괄호들의 균형이 잘 맞춰져 있는지 판단하는 프로그램

괄호는 소괄호와 대괄호로 되어있고, 문자열이 균형을 이루는 조건은 아래와 같다.

• 모든 왼쪽 소괄호는 오른쪽 소괄호와만 짝을 이루어야 한다.
• 모든 왼쪽 대괄호는 오른쪽 대괄호와만 짝을 이루어야 한다.
• 모든 오른쪽 괄호들은 자신과 짝을 이룰 수 있는 왼쪽 괄호가 존재한다.
• 모든 괄호들의 짝은 1:1 매칭만 가능하다. 즉, 괄호 하나가 둘 이상의 괄호와 짝지어지지 않는다.
• 짝을 이루는 두 괄호가 있을 때, 그 사이에 있는 문자열도 균형이 잡혀야 한다.

문자열이 주어졌을 때 균형을 이루고 있으면 "yes", 아니면 "no"를 출력

온점 하나 (".")만 입력되면 입력이 종료된다.

시간 제한: 1초

메모리 제한: 128MB

문장의 길이는 100글자보다 작거나 같다.

---

💡 문제 해결 아이디어

• 문장을 순회하며 여는 괄호일 때는 스택에 추가, 닫는 괄호는 스택의 마지막 원소와 비교
• 닫는 괄호 입력 시 스택에 원소가 있는지 확인 + 스택의 마지막 원소가 대칭되는지 확인
• 순회가 끝나고 스택에 원소가 남아있는지 확인

---

⌛️ 시간 복잡도

• O(N)

---

✅ 최종 코드

import sys
input = sys.stdin.readline

while True:
    # rstrip인 이유: 입력에 공백 + 온점과 그냥 온점은 다른 문장임. strip 사용 시 두 입력이 같다고 판별
    sentence = input().rstrip()

    if sentence == '.':
        break

    stk = []
    flag = True
    for s in sentence:
        if s == '(' or s == '[':
            stk.append(s)
        elif s == ')':
            if not stk or stk[-1] != '(':
                flag = False
                break
            stk.pop()
        elif s == ']':
            if not stk or stk[-1] != '[':
                flag = False
                break
            stk.pop()
    if stk:
        flag = False
    print("yes" if flag else "no")