백준 / 1541번 잃어버린 괄호 / Python 파이썬

 

*문제 출처는 백준에 있습니다.

문제 제목: 1541번 잃어버린 괄호

문제 사이트: https://www.acmicpc.net/problem/1541

1541번: 잃어버린 괄호

 

시간 제한메모리 제한제출정답맞힌 사람정답 비율

2 초

128 MB

69265

36858

28955

52.529%

문제

세준이는 양수와 +, -, 그리고 괄호를 가지고 식을 만들었다. 그리고 나서 세준이는 괄호를 모두 지웠다.

그리고 나서 세준이는 괄호를 적절히 쳐서 이 식의 값을 최소로 만들려고 한다.

괄호를 적절히 쳐서 이 식의 값을 최소로 만드는 프로그램을 작성하시오.

입력

첫째 줄에 식이 주어진다. 식은 ‘0’~‘9’, ‘+’, 그리고 ‘-’만으로 이루어져 있고, 가장 처음과 마지막 문자는 숫자이다. 그리고 연속해서 두 개 이상의 연산자가 나타나지 않고, 5자리보다 많이 연속되는 숫자는 없다. 수는 0으로 시작할 수 있다. 입력으로 주어지는 식의 길이는 50보다 작거나 같다.

출력

첫째 줄에 정답을 출력한다.

예제 입력 1 복사

55-50+40

예제 출력 1 복사

-35

예제 입력 2 복사

10+20+30+40

예제 출력 2 복사

100

예제 입력 3 복사

00009-00009

예제 출력 3 복사

0

출처

• 문제를 번역한 사람: baekjoon
• 잘못된 조건을 찾은 사람: windflower

알고리즘 분류

• 수학
• 문자열
• 그리디 알고리즘
• 파싱

---

나의 풀이 (스택자료구조 사용)

스택을 활용해서 앞에 마이너스 연산자가 있고, 뒤에 플러스 연산자가 있으면

예시 : 1-2+6

에서 2+6 에 괄호를 해주어야 최소값이 나올 것이다.

따라서 플러스 연산자가 연속되면 해당 피연산자들을 모두 더해주고 최종적으로 괄호로 묶어 eval 으로 연산하였다.

 

import sys

input = sys.stdin.readline


n = input().strip('\n')
cal = []


num = ""
for i in n:
    if (i == '-' and num == "") or i.isnumeric() :
        num += i
    
    else:
        cal.append(int(num))
        num = ""
        cal.append(i)
if num:
    cal.append(int(num))

stack = []
plus = []
for i in range(len(cal)):
    if plus == []:
        if cal[i] == "+":
            node = stack.pop()
            plus.append(node)
            stack.append("(")
        else:
            stack.append(cal[i])
    else:
        if cal[i] == "-":
            stack.append(sum(plus))
            stack.append(")")
            stack.append(cal[i])
            plus = []
        elif cal[i] != '+' and cal[i] != '-':
            plus.append(cal[i])

        if i == len(cal)-1:
            stack.append(sum(plus))
            stack.append(")")
            plus = []    
answer = ""
for i in stack:
    answer += str(i)
print(eval(answer))

 

다른 풀이 1

괄호 문제라고 굳이 문제에 괄호를 안넣어주고도 간단히 풀 수 있다 . ^^.. 너무 복잡하게 생각하지 말자

exp = input().split('-')
num = []
for i in exp:
    cnt = 0
    sum = i.split('+')
    for j in sum:
        cnt += int(j)
    num.append(cnt)
ans = num[0]
for i in range(1, len(num)):
    ans -= num[i]
print(ans)

다른 풀이 (숏코딩)

a,*b=[sum(map(int,s.split('+')))for s in input().split('-')];print(a-sum(b))

b를 *리스트로 받아서 연산자로 합산하고 프린트했당

숏코딩보고 좌절했는데 하지만 내 코드가  더 빨랐죠?

---