BOJ 1541 - 잃어버린 괄호

folder_open Algorithm / BOJ / silver | date_range 29 Dec 2024

sell #BOJ #1541 #silver #python #파이썬 #코딩테스트 #알고리즘

맨 위로

• 문제 링크
• 구현
• 코드

문제 링크

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

구현

문제를 읽어보면, 맨 앞은 숫자로 고정되어있다고 한다. 즉, 맨 앞은 무조건 + 이다.

그리고 식의 결과가 가장 작으려면 -의 뒤에 있는 모든 식은 +가 되어야한다.
결과적으로, 식의 맨 뒤에서부터 스택에 push하다가, -가 나오면 모두 빼준다. 맨 마지막에 스택에 남아있는 숫자는 무조건 + 이다.

코드

from sys import stdin
input = lambda : stdin.readline().strip()


def split_(formula: str):
    return_arr = []
    num = ''
    for s in formula:
        if s == '+' or s== '-':
            return_arr.append(int(num))
            num = ''
            return_arr.append(s)
        else:
            num += s
    return_arr.append(int(num))
    return return_arr
    
if __name__ == '__main__':
    formula = input()
    split_list = split_(formula)
    stack = []
    res = 0
    for i in range(len(split_list) - 1, -1, -1):
        if isinstance(split_list[i], int):
            stack.append(split_list[i])
        else:
            if split_list[i] == '-':
                while stack:
                    res -= stack.pop()
    while stack:
        res += stack.pop()
    print(res)