[python] 1541, 잃어버린 괄호

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

1541번: 잃어버린 괄호

 

[문제]

세준이는 양수와 +, -, 그리고 괄호를 가지고 식을 만들었다. 그리고 나서 세준이는 괄호를 모두 지웠다.

그리고 나서 세준이는 괄호를 적절히 쳐서 이 식의 값을 최소로 만들려고 한다.

괄호를 적절히 쳐서 이 식의 값을 최소로 만드는 프로그램을 작성하시오.

 

[입력]

첫째 줄에 식이 주어진다. 식은 ‘0’~‘9’, ‘+’, 그리고 ‘-’만으로 이루어져 있고, 가장 처음과 마지막 문자는 숫자이다. 그리고 연속해서 두 개 이상의 연산자가 나타나지 않고, 5자리보다 많이 연속되는 숫자는 없다. 수는 0으로 시작할 수 있다. 입력으로 주어지는 식의 길이는 50보다 작거나 같다.

 

[출력]

첫째 줄에 정답을 출력한다.

 

[예제]

 

[풀이]

• 기본 아이디어
  • 수식에 '-'가 처음으로 등장하는 순간 그 뒤의 모든 값은 더해서 마이너스를 붙여주면 됨
    1. 55 - 50 + 40 -> 55 - (50 + 40) : '-'로 묶어주면 됨
    2. 55 - 50 - 40 -> 괄호로 묶지 않아도 값은 같음
  • '-'가 처음으로 등장하기 이전의 수식은 무조건 '+'로 연결된 수식이기 때문에
  • (첫 '-' 이전 값의 합) - (첫 '-' 이후 값의 합) 이 최솟값이 됨
• 풀이 1 -> 처음으로 푼 풀이인데 .. 너무 복잡함

eq = input()
num = ''
eval_lst = []

for idx, word in enumerate(eq):
  if word.isdigit():
    num += word
    if idx == len(eq) - 1:
      num = num.lstrip('0')
      eval_lst.append(num)
  else:
    num = num.lstrip('0')
    eval_lst.append(num)
    num = ''
    eval_lst.append(word)

try:
  idx = eval_lst.index('-')
  eq_1 = eval_lst[:idx]
  eq_2 = eval_lst[idx:]

  eq_1 = int(eval(''.join(eval_lst[:idx])))
  eq_2 = int(eval(''.join(eval_lst[idx:]).replace('+','-')))
  print(eq_1 + eq_2)

except:
  print(eval(''.join(eval_lst)))

• '55 + 50 - 40" 처럼 하나의 문자열로 입력받은 수식을 [55, '+', 50, '-', 40] 의 형태로 변환
  • 이때, '0009'와 같은 입력값이 존재하기 때문에 lstrip('0')을 사용하여 int의 형태로 변환해줌
• 첫 '-'가 등장하는 인덱스를 찾아 이를 기준으로 앞 뒤로 리스트를 분리
  • '-'가 존재하지 않는 산식도 있기 때문에 에러가 발생할 가능성이 있음
  • 따라서 try-except 구문을 사용해 경우의 수를 분리
  • 식에 '+'만 존재하는 경우 별도의 변환 없이 모두 더해줌
• 이후 리스트 내의 숫자와 연산자를 join함수를 이용하여 결합한 뒤 eval함수를 사용하여 문자열인 수식의 결과값을 반환
  • 이때, eq_2에는 '-', '+' 부호가 섞여있기 때문에 모두 '-'로 부호를 통일시켜 산식을 완성시켜줌
• 결과적으로, eq_1 ('-'가 나오기 전 '+'로만 이루어진 산식 -> 모두 더한 값) + eq_2 ('-'가 나온 이후의 값을 모두 더한 것에 '-'를 붙여준 것) => 최솟값이 됨
• <<< 문제점 >>> : '00009'와 같은 형태의 수를 eval함수에 적용시키기 위해서는 왼쪽의 '0'을 모두 삭제해주는 과정이 필요함 -> 이를 위해 문자열을 연산자와 숫자를 분리한 리스트로 변환해주는 방식을 사용했는데 너무 복잡해짐

 

• 풀이 2 -> 완전 간단한데 .. 시간은 더 걸림

eq = input().split('-')

result = sum(list(map(int, eq[0].split('+'))))

for i in eq[1:]:
  result -= sum(list(map(int, i.split('+'))))

print(result)

• 전체 산식을 '-' 기준으로 split -> 리스트로 변환되었을 때 리스트 내 모든 원소들이 '+'로 이루어지거나 숫자로만 이루어진 수시기 될 것
• result는 결과값을 저장하는 변수 -> '-'이 등장하기 이전 식의 총합을 초기값으로 저장
• 리스트 내 원소를 for문으로 하나씩 받아 '+' 기준으로 split해줌 -> '+' 기준으로 split된 리스트 생성됨
• '+' 기준으로 split된 리스트의 원소들을 map(int,)를 사용하여 int형으로 변환 후 해당 리스트 내의 값의 총합을 sum 함수를 이용해 계산
• 이를 result에서 계속 빼주면 결국 result가 최솟값이 됨