스택의 활용- 바킹독 유튜브

아래의 문제들을 접하고 풀어보았다. 강의 전체적으로 문제에 대한 설명과 괄호쌍 문제를 어떻게 풀면 좋은지 설명만 있어서 딱히 정리할 건 없었다.

boj - 2504

더 코드를 간결하고 깔끔하게 짤 수도 있을 거 같은데 스택의 구조를 파악하는게 우선이라고 생각해서 돌아가는 코드를 짜봤다. 지금처럼 스택에 구해진 값을 넣는 것 보다 합계 값, 곱셈 값을 구해서 더하고 곱하는 방식으로 풀 수 있을 것 같다.

import sys

check_string = input()


SCORE = 1
BRACKET = 0

bracket_map = {
    ")" : ["(", 2],
    "]" : ["[" ,3]
}

check_opened_bracket = ["(", "["]

stack = []
for char in check_string:
    if char in check_opened_bracket:
        stack.append(char)

    elif char in bracket_map:
        cur_num = 0
        # 닫는 괄호가 나왔는데 안에 숫자가 있다면 숫자들을 모두 더해주어야 한다.
        while stack and type(stack[-1]) == int:
            cur_num += stack.pop()
        # 열린 괄호를 찾아 일치하는지 보고 pop해준다.    
        if stack and stack[-1] == bracket_map[char][BRACKET]:
            stack.pop()
            if cur_num:
                stack.append(cur_num * bracket_map[char][SCORE]) 
            else: 
                stack.append(bracket_map[char][SCORE])
        else:
            print(0)
            sys.exit(0)

# 숫자 형태로 다 만들어진다면 sum을 통해 값을 도출 할 수 있고 아니라면 stack에 괄호가 남은 것으로 0을 프린트 해주면 된다.
try:
    print(sum(stack))
except:
    print(0)

boj - 10799

닫히는 괄호가 레이저를 쏘는 괄호인지 아니면 막대기의 길이를 나타내는 괄호인지 파악하여 닫히는 괄호라면 1을 더해주고 레이저를 쏘는 괄호라면 스택에 남아있는 열려있는 괄호의 갯수만큼 막대기를 자르기 때문에 스택에 담긴 수만큼 정답값에 더해주고

막대기를 표시하는 괄호라면 막대기가 잘리고 난 끄트머리 부분만 남게 되므로 1을 더해주면 값을 구할 수 있다.

import sys
input = sys.stdin.readline

brackets = input().rstrip()

stack = []
answer = 0

for idx, bracket in enumerate(brackets):
    if bracket == "(":
        stack.append(bracket)
    elif bracket == ")":
        stack.pop()
        if brackets[idx-1] == "(":
            answer += len(stack)
        else:
            answer +=1
print(answer)
        

boj - 4949

열린 괄호는 스택에 담아주고 닫힌 괄호라면 스택에 담긴 마지막 값과 같은 괄호인지 확인하고 같다면 pop 아니라면 no를 프린트 해주면 된다.

bracket_map = {
    ")" : "(",
    "]" : "["
}

check_opened_bracket = bracket_map.values()
while True:
    check_string = input()
    if check_string[0] == ".":
        break
    
    stack = []
    
    for char in check_string:
        if char in check_opened_bracket:
            stack.append(char)
            
        elif char in bracket_map:
            if len(stack) != 0 and stack[-1] == bracket_map[char]:
                stack.pop()
            else: 
                print("no")
                break
                
        else: continue
    else:
        if len(stack) == 0:
            print("yes")
        else: print("no")