[백준][그리디] 잃어버린 괄호

오늘의 학습 키워드

그리디 알고리즘, 문자열

 

오늘의 회고

🌱 오늘의 문제

https://www.acmicpc.net/problem/1541

 

입력으로 주어진 문자열 중 특정 부분에 괄호를 쳤을 때 가장 작은 값을 만드는 문제이다.

입력으로는 덧셈/뺄셈 부호(+, -)와 숫자로 구성된 문자열이 주어진다.

 

 

🌱 나의 시도

마이너스 사이에 있는 덧셈 부호를 모두 괄호로 묶어서 가장 큰 값을 빼 주는 방식으로 접근하였다.

따라서 아래와 같은 흐름으로 코드가 진행된다.

1. 문자열을 돌면서 마이너스를 만나면 스위치가 켜진다.

2. 스위치가 켜지면 마이너스 사이의 값들을 스택에 넣어 모두 더해준 다음, 스택의 값을 전체에서 빼준다.

formular = input()

switch = False # 마이너스 부호를 만나면 덧셈 부호를 뺄셈으로 바꿔줄 스위치
st = 0 # 피연산자(숫자)의 시작 위치
answer = 0 # 최종 정답 값

stack = []
for i, c in enumerate(formular):
    if c == '-' or c == '+': 
        operand = int(formular[st:i]) # 피연산자 값
        stack.append(operand)
        st = i+1 # 피연산자 위치 재정의
        if c == '-':
            answer = answer-sum(stack) if switch else answer+sum(stack)
            stack = []
            switch = True
        
        
stack.append(int(formular[st:]))
answer = answer-sum(stack) if switch else answer+sum(stack)
        
print(answer)

 

 

위 코드로 1차적으로 구현을 마치고 채점에 통과하였다.

그런데 코드가 깔끔하지 못한 것 같아 정리하는 과정에서 아래와 같은 결론을 도출할 수 있었다.

 

괄호를 쳐서 그 합을 빼준다는 것은, 괄호 내부의 각각의 항에 -1을 곱해서 음수 항으로 변경해준다는 것과 동일한 의미로 볼 수 있다.

따라서 스택에 넣어서 그 합을 빼 줄 필요 없이, 덧셈 연산이 아닌 마이너스 연산으로 수행해주면 된다.

 

또한 한 번 이상 마이너스 연산이 등장한 경우, 마이너스 연산 등장 이후의 양수항은 모두 음수항으로 변경된다.

즉, 스위치가 다시 꺼지는 경우가 없다는 것을 확인할 수 있었다.

 

위 결론을 통해 아래와 같이 코드를 좀 더 간소화할 수 있었다.

 

'''
모두 합쳐서 뺀다 = 더하지 않고 뺀다
-> 마이너스 뒤에 괄호를 친다는 것은 이후 항을 음수항으로 바꾸는 것이므로 마이너스 등장 후부터 빼주면 됨!
'''
formular = input()

switch = False
st = 0
answer = 0

for i, c in enumerate(formular):
    if c == '-' or c == '+':
        operand = int(formular[st:i])
        st = i+1
        if switch:
            answer -= operand
        else:
            answer += operand
            if c == '-': switch = True

operand = int(formular[st:])
answer = answer-operand if switch else answer+operand

print(answer)

 

 

문자열을 따라 반복문을 돌면서 연산자가 나타날 때마다 이전에 등장했던 피연산자에 대해 처리하므로, 시간 복잡도는 O(n)으로 가능하다.

다만 반복문 내부에서 마지막 연산자에 대해 처리해주지 않으므로 반복문 바깥에서 추가로 처리해주었다.

그러나 이것은 O(1)이므로 시간 복잡도에 영향을 주지 않는다.

 

 

오늘의 후기

한 번 더 코드를 간소화할 수 있는 방법이 있을 것 같은데 잘 떠오르지 않는다.

그래도 코드를 제출하고 마치는 것이 아니라, 다시 검토해보면서 개선해보는 것은 좋은 습관인 것 같다.

나중에 다시 이 포스팅을 다시 보게 될 때에는 이 코드를 더 간결하게 혹은 더 효율성 좋게 짤 수 있을 것이다.

 

끝!