알고리즘 스터디 - 백준 1541번 : 잃어버린 괄호

문제 해석

세준이가 양수, +, -, 괄호로 식을 만드는데 이 식의 값을 최소로 만드는 것이 목적이다.

1. 55-50+40 일 때

• 마이너스가 나오면 건너뛰고 뒤에 있는 숫자를 최대로 만들어서 계산
• 1) 50+40 계산 2) 55-90 진행

2. 10+20+30+40 일 때

• 이 경우 마이너스가 나오지 않았기에 다 더해준다.

3. 00009-00009 일 때

• 0 앞에 숫자가 나오지 않고 1) 숫자가 없고 2) +, - 뒤에 바로 0이 나오면 0을 버린다.

새로운 케이스 10-20+30-40 일 때

• 1) 10 입력 2) - 건너 뜀 3) 새로운 - 가 나올 때까지 더함
• 10-50 이후 -를 건너 뛰고 숫자를 받고 새로운 연산자가 나오지 않으면 기존 결과에 -40을 진행

알고리즘 코드

1) 처음에 구현 방식으로 구했던 코드

calculate = list(input())

answer = []
num = ""

while len(calculate) > 0:
    word = calculate.pop(0)
    if word == "+":
        answer.append(int(num))
        num = ""
    elif word == "-":
        answer.append(int(num))
        num = ""
        answer.append("-")
    else:
        num += word

answer.append(int(num))
ans = answer[0]
minus = False

if '-' not in answer:
    print(sum(answer))
else:
    for i in answer[1:]:
        if i == "-":
            minus = True
            continue

        if minus:
            ans -= i
        else:
            ans += i
    
    print(ans)

2) 다른 사람 코드 보고 따라했을 경우

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

둘다 메모리나 시간이 각각 30864KB, 68ms로 같았다.
1. 처음 방식은 +를 없애고 -만 남겼을 때이고
2. 두번째 방식은 -를 없애고 +를 기준으로 토큰화하여 문제를 풀었다.
두번째 방식이 O(N^2)로 더 오래 걸릴 것 같았는데 시간이 똑같아서 살펴보니 식의 길이가 50 이하라서 그런건가 싶었다.