[Algorithm] 1541. 잃어버린 괄호

1541: 잃어버린 괄호 (그리디)

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

• 문제 티어 : S2
• 풀이 여부 : Failed → Solved
• 소요 시간 : 35:14

정답 코드

import sys
input = sys.stdin.readline

opr = input().rstrip()
parts = opr.split('-')
res = sum(map(int, parts[0].split('+')))
for part in parts[1:]:
  res -= sum(map(int, part.split('+')))

print(res)

접근 방식

이 문제를 풀이하는 핵심 아이디어는

1. - 을 기준으로 수식을 분리
2. - 이후의 모든 수를 괄호로 묶어 한번에 빼주기

로 볼 수 있다.

따라서 입력값을 - 부호를 기준으로 나눠서 parts 배열에 저장한다.
ex) 55+10-50+40-20+70 → ['55+10', '50+40', '20+70']

그 다음 -부호가 하나도 없어 parts 배열의 길이가 1인 경우 res값을 한번만 갱신해주고,
1 이상인 경우 parts[0] 이후의 값을 빼주며 최솟값을 산출한다.

접근 시행착오(+ 코드)

괄호를 추가해 값을 최소로 만들기 위해서는, -연산자가 적용되는 범위를 최대로 가져가야 한다.
그리디로 접근해서 - 부호를 찾아 minus_idx 에 뺄셈부호의 인덱스를 저장해주고, 저장된 인덱스를 기반으로 문자를 추가하는 방식으로 접근했다.

최종적으로 문자열 연산식의 계산결과를 리턴하는 함수를 사용해 계산값을 도출하려고 했다.

하지만!! 괄호를 추가하는 과정에서 오류가 있었고, 예제입력3과 같이 0으로 시작하는 값의 연산에서 syntax error가 발생했다.

import sys
input = sys.stdin.readline

opr = list(input().rstrip())
minus_idx = []
for i in range(len(opr)): # worst : O(50)
  if opr[i] == '-':
    minus_idx.append(i) # - 위치 인덱스 기록 (값을 최소로 만들기 위해)

if minus_idx: # - 부호가 1개 이상 있는 경우
  opr.insert(minus_idx[0]+1, '(') # - 부호 뒤에 괄호 추가
  opr.append(')') # 연산식 마지막에 닫는 괄호 추가(여는괄호 추가를 고려한 위치)
  
  for i in range(len(minus_idx)-1):
    opr.insert(minus_idx[i]+1, '(')
    opr.insert(minus_idx[i+1]+2, ')')

# print(minus_idx)
# print(opr)
eval_opr = eval(''.join(opr))
print(eval_opr)

배운점 또는 느낀점

이상하게 그리디가 너무 안풀린다!!! 그리디 문제 특성을 잘 생각해서 핵심 구현방법을 잘 파악하자!!!