Week 01 ~ 04 : 알고리즘 문제 풀이

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

정글러 2021. 11. 27. 15:08
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
= input()
= 0
sum = 0
sign = 1
while i < len(l) : 
    n = ''
    while i < len(l) and l[i] != '+' and l[i] != '-' : 
        n = n + l[i]
        i = i + 1
    num = int(n)
    if i < len(l) and l[i] == '+' : 
        sum = sum + num * sign
        i = i + 1
    if i < len(l) and l[i] == '-' : 
        sum = sum + num * sign
        sign = -1
        i = i + 1
print(sum + num * sign)
 
cs

IDEA

많은 경우를 고려해야 할 것 같지만 그리디 문제이므로 문제를 해결하는 하나의 규칙성이 있다.

연산이 +, - 뿐이므로, 뺄 수 있는 수는 모두 뺀다면 그것이 최솟값이 될 것이다.

 

가장 처음 나온 첫번째 - 이후로는 모든 수를 괄호를 이용하야 음수로 만들 수 있다.

-가 한개라면 -뒤로 전부 하나의 괄호로 묶으면 되고, -가 여러개라면 -와 -의 사이마다 하나의 괄호로 묶으면 된다.

 

line 7 ~ 10

인풋받은 i번째 문자가 숫자가 아닌게 나올때까지 그 숫자문자들을 하나로 합친다.

+나 -가 나온다면 지금까지 합친 str을 하나의 int num으로 바꾼다.

 

line 11 ~ 14

sum에 num * sign을 더한다. sign은 초깃값이 1(plus)이지만, 한번이라도 -가 나오면 -1이 된다. (line 16)

즉 최초의 -가 나오기 전까진 num을 더하고, 최초의 - 이후로는 모두 num을 뺀다.

 

line 18

i가 str의 마지막까지 도달하여 while문이 끝나면, 마지막으로 완성된 num 하나는 아직 sum에 포함되지 않았다.

이를 합쳐준 뒤 출력한다.