BOJ #1541 잃어버린 괄호

읽기 전

• 불필요한 코드나 잘못 작성된 내용에 대한 지적은 언제나 환영합니다.
• 개인적으로 배운 점을 정리한 글입니다.

문제 링크

문제 1541. 잃어버린 괄호

문제 풀이

처음 풀이했을 땐 분할 정복으로 가능한 경우의 수를 list에 저장한 뒤 min()으로 가장 작은 값을 출력해봤으나 연산자가 많아질 수록 경우의 수도 기하급수적으로 늘어나 시간 초과가 발생하였다. 문제를 다시 읽어보면 연산자는 +와 -만 존재한다고 명시되어 있다. 그렇다면 더하는 건 최소로 더하고 빼는 수를 가장 크게 만들어야 한다. 그렇다면 - 연산자와 다음 - 연산자 사이는 모두 더해지는 값이므로 이 부분에 대해서만 괄호로 묶어주면 + 연산자만 존재하지 않는 한 첫 번째 값에서 항상 값을 빼는 형태로 완성될 것 같다.

python 코드-1(시간초과)

def compute(left, right, value):
    result = []
    for l in left:
        for r in right:
            result.append(eval(str(l) + value + str(r)))
    return result

def solve(expression):
    if expression.isdigit():
        return [int(expression)]
    sol = []
    for idx, value in enumerate(expression):
        if value in '+-':
            left = solve(expression[:idx])
            right = solve(expression[idx + 1:])
            sol.extend(compute(left, right, value))
    return sol

expression = input()
sol = solve(expression)
print(min(sol))

python 코드-2

expression = input()
exp_list = expression.split('-') # - 연산자로 구분
for i in range(len(exp_list)): # 나머지 식들에 대해
    exp_list[i] = sum(map(int, exp_list[i].split('+'))) # 모두 덧셈 처리
sol = exp_list[0] # 초기 값은 항상 양수
for item in exp_list[1:]:
    sol -= item # 첫번째 값에서 나머지 원소들은 모두 뺄셈
print(sol)

오히려 알고리즘으로 어렵게 풀었을 때 시간초과가 나오는 문제였다.