BOJ 1541 잃어버린 괄호
https://www.acmicpc.net/problem/1541
시간 2초, 메모리 128MB
input :
- 식은 ‘0’~‘9’, ‘+’, 그리고 ‘-’만으로 이루어져 있고, 가장 처음과 마지막 문자는 숫자이다.
output :
- 정답을 출력
조건 :
- 세준이는 괄호를 적절히 쳐서 이 식의 값을 최소로 만들려고 한다.
가장 최소를 만드려면 어떻게 해야 할까..
더하기를 우선적으로 다하고 빼버리면 음수 쪽으로 넘겨버릴수 있다.
'-'를 이용해서 파싱을 한 후에.
숫자의 모양이 언제나 '숫자 + 숫자' 인 것이 아니라
'숫자 + 숫자 + 숫자' 등 여러번 나올 수 있기 때문에 파싱을 할 떄 이를 리스트로 만들어서 넣자.
'+'를 가지고 있는 숫자들을 모두 더해서 temp 배열에 넣어준다.
while data:
now = data.pop(0)
if '+' in now:
in_temp = list(map(int, now.split("+")))
ret = in_temp.pop(0)
while in_temp:
a = in_temp.pop(0)
ret += a
temp.append(ret)
else:
temp.append(int(now))
그리고 더할 때는 그냥 값 1개씩 빼서 더해주고,
마지막에는 앞에서 부터 빼주면 된다.
import sys
data = list(sys.stdin.readline().rstrip().split("-"))
temp = []
while data:
now = data.pop(0)
if '+' in now:
in_temp = list(map(int, now.split("+")))
ret = in_temp.pop(0)
while in_temp:
a = in_temp.pop(0)
ret += a
temp.append(ret)
else:
temp.append(int(now))
ans = temp.pop(0)
while temp:
now = temp.pop(0)
ans -= now
print(ans)
날이 갈수록 코드가 조잡해지는 감이 없지 않아 있는데,,, 일단 뭐 더해주고, 빼줘야 하니까 뭐 어쩔 수 없다.
Author And Source
이 문제에 관하여(BOJ 1541 잃어버린 괄호), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@jsin2475/BOJ-1541-잃어버린-괄호저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)