[백준] 4949번: 균형잡힌 세상 (파이썬)

✅문제: 4949번

4949번: 균형잡힌 세상

📌개념정리

(1) 스택(Stack)

• 정의: 후입선출(LIFO, Last In First Out)의 원리로 작동하는 자료구조
• 파이썬에서는 리스트(List) 자료형을 스택(Stack)처럼 사용할 수 있음.
  • 파이썬의 리스트가 동적 배열로 구현되어 있어서 스택의 핵심 연산인 푸시(push, 요소를 추가하는 연산)와 팝(pop, 최근에 추가된 요소를 제거하는 연산)을 기본적으로 지원하기 때문.
• 파이썬에서 스택 사용
  1. 푸시(Push): 파이썬의 리스트에서는 append() 메소드를 사용하여 리스트의 끝에 요소를 추가함.
  2. 팝(Pop): 파이썬 리스트의 pop() 메소드는 리스트의 마지막 요소를 제거하고 그 값을 반환함.
  3. 피크(Peek): 스택의 최상단(마지막에 추가된) 요소를 조회하는 연산. 파이썬 리스트에서는 인덱싱을 사용하여 마지막 요소를 직접 조회할 수 있음(list[-1]).

▲ 예제 입력 1: 괄호 검사 성공

📌문제풀이

주어진 문자열의 괄호가 올바르게 짝지어 졌는지, 문장이 온점으로 끝나는지 판별하는 문제임. 괄호는 소괄호 ()와 대괄호 [] 두 종류가 있으며, 괄호의 종류별로 짝이 맞아야 하고, 괄호의 순서도 올바르게 닫혀야 함.

 

먼저, 파이썬 코드를 어떻게 작성할지 로직을 고민해야 함.

1. 각 줄을 입력받아 순회
2. 각 줄에 대해 문자를 순회하면서, 괄호가 나오면 스택에 푸시
3. 닫는 괄호가 나오면, 스택에서 하나를 팝하여 마지막으로 열린 괄호와 짝이 맞는지 확인
4. 모든 문자를 순회한 후, 스택이 비어있으면 "yes", 아니면 "no" 출력
5. 입력의 끝을 나타내는 '.'이 단독으로 입력될 때까지 반복

while True:
    s = input()
    if s == '.':
        break
    stack = []
    balanced = True	# 문자열 내의 괄호가 올바르게 짝지어 졌는지 체크
    for char in s:
    	# 여는 괄호인 경우 푸시
        if char in '([':
            stack.append(char)
        # 닫는 괄호 ')'인 경우
        elif char == ')':
            # 스택이 비어있거나 마지막으로 추가된 괄호가 '('이 아닌 경우
            if not stack or stack[-1] != '(':
                balanced = False
                break
            stack.pop()
        # 닫는 괄호 ']'인 경우
        elif char == ']':
            # 스택이 비어있거나 마지막으로 추가된 괄호가 '['이 아닌 경우
            if not stack or stack[-1] != '[':
                balanced = False
                break
            stack.pop()
    if balanced and not stack:
        print("yes")
    else:
        print("no")

1. 사용자로부터 한 줄을 입력받음.
2. 입력된 문자열이 '.' 한 개만 있을 경우 반복문을 종료함.
3. stack = [] 리스트를 스택으로 사용하여 열린 괄호를 저장함.
4. for문으로 입력받은 문자열의 각 문자를 순회함.
   1. 여는 괄호가 나오면 스택에 푸시함.
   2. 닫는 괄호가 나오면 스택에서 마지막으로 열린 괄호를 팝하여 짝이 맞는지 확인함. 짝이 맞지 않으면 반복문을 종료함.
5. 모든 괄호가 올바르게 닫혔는지 확인함.

📌후기

• 처음 문제를 접했을 때, 비슷한 문제를 풀어본 경험이 있어 쉽다고 생각했음.
• 소괄호와 대괄호를 처리하는 로직을 설계하는 것이 조금 어려웠음. 입력이 '.' 한 개로만 구성될 때 반복을 종료하는 조건을 어떻게 처리할지도 고민했던 것 같음.
• 파이썬의 리스트를 스택으로 활용하는 것 편하긴 하지만, 스택을 어떻게 구현할 수 있는지도 공부해야겠음.

📌참고자료

1) 위키독스, "04. 파이썬으로 스택 구현하기", https://wikidocs.net/192069

2) 위키독스, "02. 스택과 큐", https://wikidocs.net/198491