[백준/Python] (S2)1541 - 잃어버린 괄호

잃어버린 괄호 성공

 

 

1541번: 잃어버린 괄호

 

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

2 초

128 MB

84537

45928

35909

53.698%

문제

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

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

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

입력

 

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

출력

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

예제 입력 1 복사

55-50+40

예제 출력 1 복사

-35

예제 입력 2 복사

10+20+30+40

예제 출력 2 복사

100

예제 입력 3 복사

00009-00009

예제 출력 3 복사

0

 

추가예제

예제 입력 1 복사

1-1+1-1+1

예제 출력 1 복사

-3

예제 입력 2 복사

0+2-0

예제 출력 2 복사

2

---

일단 이 문제를 처음 봤을때 숫자를 따로 리스트에 저장해두고 리스트를 오름차순 정렬해서 구하려고 했다.

 

문제를 잘 읽어보면 주어진 식 그대로 사용하라고 해서 위의 생각을 버리고 주어진 식 그대로 문자열로 옮겨와 숫자는 따로 파싱해서 사용하였다.

 

식이 있으면 answer와 temp 변수 두개를 만들었고, minusFlag를 두어 - 기호를 만났을 때 temp에 수를 저장 후 값을 처리하였고, 아니라면 answer에 바로 더하는 식으로 처리하였다.

#1541 잃어버린 괄호 (그리디, 수학, 문자열, 파싱)
import sys
s = sys.stdin.readline()

num = [] #식을 담을 배열
n = '' #식에 사용된 숫자를 파싱하기 위한 변수

minusFlag = False #식에 - 기호가 있었는지 판단하는 플래그

#일단 식을 파싱한다.
for i in s:
    if not(i == '+' or i == '-'): #기호가 아니라면
        n += i #숫자를 문자열로 일단 저장
    else: #기호라면
        num.append(int(n))
        n = ''
        num.append(i)
num.append(int(n)) #마지막 저장된 수도 추가.

#구현 로직 진행
answer = num[0] #첫번째는 무조건 숫자일거고, 이 수는 어쨌든 어떠한 연산도 들어가지 않는다.
#따라서 answer에 저장한다.
temp = 0

for i in range(1,len(num)):
    if not(num[i] == '+' or num[i] == '-'):
        if minusFlag:
            temp += num[i]
        else:
            answer += num[i]
        # print("answer:",answer,"temp:",temp)

    else:
        if num[i] == '-':
            minusFlag = True
            answer -= temp
            temp = 0
   
#여기까지 진행했다면, 마지막에 temp에 남아있는 수도 전부 처리해주어야한다.
if minusFlag:
    answer -= temp
else:
    answer += temp
    
print(answer)

 

추가로 다른 사람의 풀이 몇개를 첨부함. (코드가 아닌 문제 해결을 떠올린 방법을 비교해보자.)

https://puleugo.tistory.com/29

[백준 1541] 잃어버린 괄호 해설 및 풀이 (파이썬)

 

https://edder773.tistory.com/242

[백준 1541] 잃어버린 괄호(python)

 

https://dduniverse.tistory.com/entry/%EB%B0%B1%EC%A4%80-1541-%EC%9E%83%EC%96%B4%EB%B2%84%EB%A6%B0-%EA%B4%84%ED%98%B8-%ED%8C%8C%EC%9D%B4%EC%8D%AC-python

백준 1541 | 그리디 | 잃어버린 괄호 [파이썬 python]