🐨백준 파이썬]# 1541번-잃어버린 괄호(그리디 알고리즘)

"-" 뒤에 있는 수는 모두 더한다.

eval을 쓰면 00009같은 것 때문에 에러가 난다.

def calc(exp):
    return sum(map(int,exp.split("+")))

expression = input()

if "-" in expression:
    a = expression.split("-")

    front = calc(a[0])
    back = [calc(x) for x in a[1:]]
    result = front - sum(back)
else:
    result = calc(expression)
print(result)

그리디라고 하는데.... 이렇게밖에 방법이 안 떠오른다 ㅠㅠ

이게 왜 그리디인지 알아보자.

 

주어진 코드는 먼저 입력된 수식에서 "-" 기호를 기준으로 분리하여, 각 부분의 합을 계산한 후, "-"를 기준으로 앞부분에서 뒷부분의 합을 빼는 로직을 구현하고 있습니다. "+" 기호가 포함된 부분은 calc 함수를 사용하여 합을 계산합니다.

그리디 알고리즘(Greedy Algorithm)을 적용하기 위해, 최적의 접근 방식을 고려해야 합니다. 이 문제의 경우, 그리디 알고리즘의 적용은 주어진 수식을 효율적으로 계산하여 최대한 빨리 최적의 결과를 도출하는 것을 의미합니다. 여기서는 "-" 기호 뒤에 오는 모든 수를 최소화하는 방향으로 접근할 수 있습니다. 즉, 첫 번째 "-"가 나타난 이후의 모든 숫자를 하나의 그룹으로 묶어 그 합을 최초로 나타난 부분의 합에서 빼는 것입니다. 이렇게 하면 최소한의 점수를 얻을 수 있으며, 이는 곧 최적해를 의미합니다.

아래는 그리디 알고리즘을 적용한 코드입니다. 첫 번째 "-"를 기준으로 앞뒤를 나누고, 뒷부분에 있는 모든 숫자들을 하나의 그룹으로 합산한 다음, 앞부분에서 이 값을 빼는 방식으로 계산합니다.

def calc(exp):
    return sum(map(int, exp.split("+")))

def calculate_greedy(expression):
    if "-" in expression:
        parts = expression.split("-")
        front = calc(parts[0])
        back_sum = sum(calc(part) for part in parts[1:])
        result = front - back_sum
    else:
        result = calc(expression)
    return result

# 예제 입력으로 테스트
test_expressions = [
    "55-50+40",
    "10+20-30+40-50+60",
    "00009-00009"
]

results = [calculate_greedy(exp) for exp in test_expressions]
results

그리디 알고리즘을 적용한 코드를 사용하여 테스트한 결과는 다음과 같습니다:

• "55-50+40" 수식에 대한 결과는 -35입니다.
• "10+20-30+40-50+60" 수식에 대한 결과는 -150입니다.
• "00009-00009" 수식에 대한 결과는 0입니다.

이는 각각의 수식을 그리디 알고리즘으로 접근하여, 첫 번째 "-" 이후의 모든 값을 하나의 그룹으로 합산하고, 이를 첫 번째 부분의 값에서 빼서 최적의 결과를 도출한 것입니다.

 

그리디로 바꿔 달라고 해서 결과를 보니 내가 짠 게 이미 그리디 알고리즘이었다.....