백준 1541번 잃어버린 괄호

정보

문제 바로가기 [클릭]

난이도: Silver2

관련 개념: #수학 #문자열 #그리디알고리즘 #파싱

---

조건

시간 제한	메모리 제한
2 초	128 MB

---

문제

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

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

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

---

입력

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

---

출력

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

---

예제 입출력 1

입력

55-50+40

출력

-35

---

예제 입출력 2

입력

10+20+30+40

출력

100

---

예제 입출력 3

입력

00009-00009

출력

0

---

코드(파이썬)

line = input().split('-')
mid_sum = []

for each in line:
    tmp_num = ''
    tmp_sum = 0
    
    for ch in each:
        if ch == '+':
            tmp_sum += int(tmp_num)
            tmp_num = ''
        else:
            tmp_num += ch
    tmp_sum += int(tmp_num)
    
    mid_sum.append(tmp_sum)

result = mid_sum[0] - (sum(mid_sum[1:]) if len(mid_sum) > 1 else 0)

print(result)

---

특이사항

• 미리 합을 계산하고, 그 값을 이용하는 방식 사용
• 내 코드(88,516KB, 420ms)에 비해 우수한 코드(바로가기, 33,800KB, 92ms)와 비교

  • import sys
    
    s = sys.stdin.readline().split('-')
    
    for i in s:
        tmp = sum(list(map(int,i.split('+'))))
        try:
            res -= tmp
        except:
            res = tmp
    
    print(res)    
    

  • ”-“를 기준으로 나누고, 나머지를 더한다는 과정 동일
  • 문자열 파싱
    • 기존: tmp_num 이용해 각각
    • 개선: map 이용해 한 번에

---

참고문헌

-