백준 4949번 균형잡힌 세상 - Python

devmin24·2021년 3월 12일
2

⏳ 도전! 알고리즘

목록 보기
3/32

문제 링크 : https://www.acmicpc.net/problem/4949

입력된 문장에 소괄호("()")와 대괄호 ("[]")가 균형이 잘 맞는지
yes or no 로 출력하는 문제이다.

이번 문제에서는 스택을 사용하면 된다.
역시 개념을 모를 땐, 구글링과 강의가 답이다. 그럼 한번 찾아보자.

스택

스택(stack)은 제한적으로 접근할 수 있는 나열 구조이다. 그 접근 방법은 언제나 목록의 끝에서만 일어난다.
스택은 한 쪽 끝에서만 자료를 넣거나 뺄 수 있는 선형 구조(LIFO - Last In First Out)으로 (즉, 후입선출법, 항아리구조) 되어 있다. 자료를 넣는 것을 '밀어넣는다' 하여 푸쉬(push)라고 하고 반대로 넣어둔 자료를 꺼내는 것을 팝(pop)이라고 하는데, 이때 꺼내지는 자료는 가장 최근에 푸쉬한 자료부터 나오게 된다. <위키백과>

풀이

  1. "."은 입력의 종료조건이다.
  2. stack 리스트를 만들어서 먼저 발생된 시작되는 괄호를 저장해주고,
    짝이 맞는 괄호가 생기면 .pop으로 리스트를 비워준다.
  3. 짝이 맞지 않는 괄호가 생기면 stack 리스트를 그대로 둔다.
  4. stack의 리스트가 비어있으면 yes를 출력하고, 비어있지 않으면
    no를 출력한다.

해답

while True :
    a = input()
    stack = []

    if a == "." :
        break

    for i in a :
        if i == '[' or i == '(' :
            stack.append(i)
        elif i == ']' :
            if len(stack) != 0 and stack[-1] == '[' :
                stack.pop() # 맞으면 지워서 stack을 비워줌 0 = yes
            else : 
                stack.append(']')
                break
        elif i == ')' :
            if len(stack) != 0 and stack[-1] == '(' :
                stack.pop()
            else :
                stack.append(')')
                break
    if len(stack) == 0 :
        print('yes')
    else :
        print('no')
profile
꾸준함, 열정 한 가득 챙겨 끝없는 목표를 향해 달려가는 개발자👩‍💻

0개의 댓글