[백준 1541번] 잃어버린 괄호 - python

문제 링크

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

1541번: 잃어버린 괄호

풀이 

- 그리디 문제 

- + 연산을 먼저 해준 다음에 - 연산을 해주면 값을 최소로 만들 수 있다. 

- 큐를 사용하여 풀이 

- data 는 등장하는 숫자 저장 

- c는 등장하는 연산자 저장 

1. 입력받은 문자열 s에 대하여 숫자면 num = '' 에 덧붙이고, 연산자면 c에 저장한다. 

연산자가 등장했다는 것은 그 전에 등장한 숫자가 num에 기록되어있을 것이므로 int(num)을 data에 저장하고 

num = ""으로 다시 초기화 

2. for문이 끝나면 마지막 숫자가 num에 기록되어있으므로 int(num)을 data에 저장

3. 큐에 첫 숫자를 삽입시켜놓고 index 를 증가 시켜가며 

+ 일 경우 큐에 젤 최근에 삽입된 숫자를 빼고 다음 숫자를 더한 값을 큐에 삽입 

- 일 경우 큐에 다음 숫자 삽입 

4. 큐에는 더하기 연산을 다 하고 마이너스 연산을 할 숫자들만 저장되어 있다. 

따라서 q에서 하나씩 빼면서 마이너스 연산 실행 

from collections import deque 

s = input()

# 등장하는 숫자 저장
data =[]
# 등장하는 연산자 저장 
c = []
num =""

# 숫자와 연산자 분리해서 저장 
for i in range(len(s)):
  if s[i].isdigit():
    num += s[i] 
  else:
    data.append(int(num))
    c.append(s[i])
    num = ""

#마지막 숫자 저장 
data.append(int(num))

q = deque()
q.append(data[0])
index = 0

while index < len(data)-1 :
  
  # 더하기 연산이면 더한 값 큐에 삽입 
  if c[index] == '+':
    x = q.pop()
    q.append(x+data[index+1])
  # 빼기 연산이면 그냥 큐에 삽입 
  else:
    q.append(data[index+1])

  index += 1

answer = q.popleft()

# 빼기 연산 실행 
while q:
  answer -= q.popleft()

print(answer)

- 다른 사람 풀이를 참고 하니 아래와 같이 간결하게 풀 수 있었다. 

n = input().split('-')
result = 0
print(n)

for i in n[0].split('+'):
  result += int(i)

for i in n[1:]:
  for j in i.split('+'):
    result -= int(j) 

print(result)