[백준] 1541번 파이썬 - 그리디

문제요약 ( 1541. 잃어버린 괄호 )

주어진 수식에 적절히 괄호를 추가하여 식의 계산 결과값이 최소가 되도록 한다.

ex. 55-50+40의 경우 55-(50+40)으로 만들어주면된다.

 

1541번: 잃어버린 괄호

 

풀이를 위한 부연 설명

• - 뒤에 붙는 숫자들은 다음 - 가 나올 때 까지 최대한 많이 묶어서 더한다.
  • 더 좋은 풀이에서는 이 점을 이용하기 위해 split 함수를 사용했다.
• 주어진 수식을 연산자와 숫자로 나눠준다.
• 연산자를 하나씩 살펴보며 - 가 나올때를 기준으로 문제를 해결한다.
  • 앞에 -가 나오고 이후 +가 나왔다면 나중에 빼기 위해 따로 해당 값들을 더해준다.
  • 만약 - 가 나왔다면 그 전까지 나와서 합으로 저장하고 있던 값을 빼준다
  • -가 연속으로 나오는 경우를 보기 위해 지금까지 따로 저장한 값이 0인지를 검사해준다.
    • ex. 1-2-3+4 의 경우를 반례로 잡으면 된다.
•  모든 반복문을 돌고 마지막으로 빼야하는 값이 있는지 확인한 후 처리해준다

• 그리디 에 대한 자세한 개념 설명과 연관 문제는 다음 링크를 참고하면 된다.

[코테 알고리즘] DFS, BFS / 관련 문제

 

코드 - 개인 풀이

import sys
input = sys.stdin.readline

mathEx = input().rstrip()

nums = []
exp = []

# 수식 만들기
tmp = ""
for i in mathEx:
    if i == "+":
        nums.append(int(tmp))
        tmp = ""
        exp.append("+")
    elif i == "-":
        nums.append(int(tmp))
        tmp = ""
        exp.append("-")
    else:
        tmp += i
nums.append(int(tmp))

total = nums[0]
minusSum = 0
haveMinus = False

for i in range(len(exp)):
    if exp[i] == "-":
        if haveMinus:
            total -= minusSum
            minusSum = 0
            haveMinus = False
        else:
            haveMinus = True
        # 연속으로 - 가 나오는 경우
        if minusSum == 0:
            haveMinus = True
	
    if haveMinus:
        minusSum += nums[i+1]
    else:
        if exp[i] == "-":
            total -= nums[i+1]
        else:
            total += nums[i+1]

if minusSum > 0:
    total -= minusSum

print(total)

 

 

코드 - 더 좋은 풀이

answer = 0
A = list(map(str, input().split("-")))

def mySum(i):
    sum = 0
    temp = str(i).split("+")
    for i in temp:
        sum += int(i)
    return sum

for i in range(len(A)):
    temp = mySum(A[i])
    if i == 0:
        answer += temp
    else:
        answer -= temp

print(answer)

 

• 내 풀이가 너무 복잡해서 다른 풀이를 찾아봤다.
• - 를 기준으로 수식을 나눠서 따로 합을 계산하는 것이다.

 

기억할 점

• 무엇을 기준으로 식이 나뉘는지 다시 생각해보기
  • 문자열의 경우 split()을 적절히 이용하는 것도 능력이다.
• 예외 처리를 위한 값들을 찾는 것이 중요하다.
  • ex. 1-2-3+4와 같이 연속적으로 -가 나오는 경우를 생각하지 못했다.
  • 틀린 경우 반례를 찾기 위해 다양한 경우의 수를 확인해봐야하는 습관이 필요할 것 같다.