Python 백준 4949 균형잡힌세상 / 스택 알고리즘

Python 백준 4949 균형잡힌세상 / 스택 알고리즘

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

4949번: 균형잡힌 세상

while True:
    bracket = input()
    if bracket == ".":
        break
    bracket_stack = []
    answer = True

    for j in bracket:
        if j == "(" or j =="[":
            bracket_stack.append(j)
        elif j == ")":
            if len(bracket_stack) == 0:
                answer = False
                break
            if bracket_stack[-1] == "(":
                bracket_stack.pop()
                # )가 들어왔는데 bracket_stack의 끝 부분이 (이라면 둘다 제거
            else: # )가 들어왔는데 마지막이 [  인 경우
                answer = False
                break
        elif j == "]":
            if len(bracket_stack) == 0:
                answer = False
                break
            if bracket_stack[-1] == "[":
                bracket_stack.pop()
            else:
                answer = False
                break
    if answer and not bracket_stack:
        print("yes")
    else:
        print("no")

 

pop과 append를 빈리스트에 활용하여 푸는 스택 알고리즘 문제

 

while True:
    bracket = input()
    if bracket == ".":
        break
    bracket_stack = []
    answer = True

while문을 계속 돌리고,

1번 돌아 갈 때마다 bracket 라는 입력값을 받는 변수를 만든다.

만약 bracket 값이 . 만들어온 경우 break로 인해 바로 while문을 탈출한다.

 

. 하나만 있으면 균형이 맞다고 보기 때문이다.

 

bracket_skack이라는 빈 리스트를 만든다.

이 빈리스트에 append와 pop을 활용하여 균형이 맞는지 아닌지 계속 확인할 것,

결과값을 나타날 때 확인 해 줄 answer를 Boolean 형태로 만든다.

 

    for j in bracket:
        if j == "(" or j == "[":
            bracket_stack.append(j)
            #bracket_stack[ ( [
        elif j == ")":
            if len(bracket_stack) == 0:
                answer = False
                break
            if bracket_stack[-1] == "(":
                bracket_stack.pop()
            else:
                answer = False
                break

for문을 활용하여,

입력받은 문자값인 bracket을 반복시킨다.

만약 문자값이 (, [ 인 경우, 왼쪽에 있는거니, 따지지 말고 바로 bracket_stack에 append해준다.

 

elif

)가 올 경우 총 3개의 경우가 있다.

if - bracket_stack 빈리스트가 0일 경우, 그 앞에 (, [가 오지 않아 bracket_stack이 빈 리스트이니, 즉 짝이 맞지 않는 경우다.

이럴 경우 answer을 False로 바꿔주고 break를 통해 탈출한다.

 

만약 brack_stack[-1] 즉 bracket_stack의 마지막 원소가 "("일 경우는 서로 짝이 맞는 경우니,

brack_stack에 있는 마지막원소를 .pop()을 통해 제거해준다.

 

else - 이 경우는 j가 ")"로 들어왔는데, bracket_stack의 값이 "[" 인 경우다.

이 경우도 짝이 맞지 않으니 answer값을 False로 하고 break를 통해 탈출한다.

 

이렇게 for문의 모든 조건을 통과하면,

answer는 그대로 True인 채로 유지될 것이고,

bracket_stack은 짝이 맞는 것끼리 제거당해 빈리스트일 것이다.

 

        elif j == "]":
            if len(bracket_stack) == 0:
                answer = False
                break
            if bracket_stack[-1] == "[":
                bracket_stack.pop()
            else:
                answer = False
                break

이 경우는 ")"와 마찬가지지만, 들어오는 값이 "]"인 경우다.

 

    if answer and not bracket_stack:
        print("yes")
    else:
        print("no")

모든 조건을 만족한 채 for문을 나오고

answer값이 True, bracket_stack값이 빈 리스트일 때는 Yes,

그렇지 않은 경우는 no를 출력해주면 끝