[백준 파이썬] 1541 잃어버린 괄호

📌문제 출처
백준 단계별 문제풀이 - 그리디 알고리즘
https://www.acmicpc.net/problem/1541

1541번: 잃어버린 괄호

 

❓ 문제

 

❗ 풀이
- 빼주는 수를 가장 크게 만든다.

📗 풀이 코드

import sys
input = sys.stdin.readline

# eval 함수 사용
num_op = ['('] # 문자열을 하나의 수나 연산자로 만들어 넣어줄 리스트
num = ''
for s in input().strip():
    if s not in ['+','-'] : # 연산자가 아닐 경우
        num += s # 숫자로 된 문자열에 숫자 추가
    else : # 연산자라면
        num_op.append(str(int(num))) # 숫자로 된 문자열이 완성되었으므로 맨 앞 0 떼고 추가
        op = ')-(' if s == '-' else '+'
        num_op.append(op)
        # 지금 연산자가 -라면 괄호를 닫아서 - 연산 숫자를 최대로 만들고 다시 괄호 시작
        # +라면 그대로 +만 넣기
        num = '' # num이 새로 시작되기에 ''으로 초기화
num_op.append(str(int(num))+')')# 마지막 수 넣어주기
print(eval(''.join(num_op))) # 문자열로 만들어서 연산

# eval 사용 X
num_op = ['('] # 문자열을 하나의 수나 연산자로 만들어 넣어줄 리스트
num = ''
for s in input().strip():
    if s not in ['+','-'] : # 연산자가 아닐 경우
        num += s # 숫자로 된 문자열에 숫자 추가
    else : # 연산자라면
        num_op.append(int(num)) # 숫자로 된 문자열이 완성되었으므로 맨 앞 0 떼고 추가
        op = list(')-(') if s == '-' else ['+']
        num_op += op
        # 지금 연산자가 -라면 괄호를 닫아서 - 연산 숫자를 최대로 만들고 다시 괄호 시작
        # +라면 그대로 +만 넣기
        num = '' # num이 새로 시작되기에 ''으로 초기화
num_op += [int(num),')'] # 마지막 수, 마지막 괄호 넣어주기

ans = 0
tmp_num = 0
p_m = 1
for i in num_op: # (, ), +, -, 수 로 구성
    if i == '(':
        tmp_num = 0
    elif i == ')':
        ans += tmp_num*p_m
    elif i == '+':
        pass
    elif i == '-':
        p_m = -1
    else :
        tmp_num += i
print(ans)

📗 코드 해설

- 마이너스 부호가 나오는 순간 괄호를 시작하고 바로 다음의 마이너스 부호가 나올 때 괄호를 닫아준다.

- 마이너스 연산을 해주는 괄호 내부 연산은 모두 자연수의 덧셈이다.

- 따라서 괄호 내부의 수는 항상 최대

- 아래와 같이 항상 최소를 찾을 수 있다.

input 문자열	괄호 처리된 문자열(최소값)
1+1+1	(1+1+1)
1+1-1	(1+1)-(1)
1-1+1	(1)-(1+1)
1-1-1	(1)-(1)-(1)