백준 4949 - 균형잡힌세상

문제

알고리즘 분류)

• 자료 구조
• 문자열
• 스택

풀이

처음에는 바보같이 자료구조의 스택과 큐의 성질을 이용하지않고
여는괄호가 등장하면 count 값을 증가
닫는괄호가 등장하면 count 값을 감소 시켜
count가 0을 만족하면 'yes'를 출력하는 방법을 선택하였는데
여러가지 변수에 오류가 많았다

코드1) 실패

array=[]
while True:
    flag = -1
    array = list(input())
    if array == ['.']:
        break
    cnt_small = 0
    cnt_big = 0
    for i in array:
        
        
        if cnt_big < 0 or cnt_small < 0:
            flag=2
            break
        elif i == '(':
            cnt_small += 1
            flag = 0
        elif i == ')':
            if flag == 1 and cnt_big != 0:
                flag = 2
                break
            cnt_small -= 1
            flag = -1
        elif i == '[':
            cnt_big += 1
            flag = 1
        elif i == ']':
            if flag == 0 and cnt_small != 0:
                flag=2
                break
            cnt_big -= 1
            flag = -1
    
    if flag == 2 or cnt_small != 0 or cnt_big != 0:
        print('no')
    else:
        print('yes')

스택의 LIFO를 이용하여
여는 괄호가 등장하면 stack에 append
닫는 괄호가 등장하면 마지막 요소가 짝이 맞는지 검사하여
탐색이 끝난 시점 flag를 통해 'yes'와'no'를 판별하였다

탐색이 끝나고 stack이 비어있는지 검사해주지 않으면 '('가 마지막에 등장하였더라도
'yes'가 출력되기 때문에
예외처리를 위해 추가해 주어야 한다

소스코드

python)

array=[]
while True:
    flag = 1
    stack=[]
    array = list(input()) 
    if array == ['.']:
        break
    
    for i in array:
        if i == '(':
            stack.append(i)
        elif i == ')':
            if stack and stack[-1] == '(':
                stack.pop()
            else:
                flag = -1
                break
        elif i == '[':
            stack.append(i)
        elif i == ']':
            if stack and stack[-1] == '[':
                stack.pop()
            else:
                flag = -1
                break
    if flag == -1 or stack :
        print('no')
    else:
        print('yes')