[백준-1541] 잃어버린 괄호

문제

링크

코드

1. 처음에는 괄호를 한 쌍만 사용한다고 생각하여 코드를 작성했다.

• 틀린 코드 1

n = input()

tmp = ''
change = []
for i in n :
    if i.isdigit() :
        tmp += i
    else :
        change.append(str(int(tmp)))
        change.append(i)
        tmp = ''
if tmp != '' :
    change.append(str(int(tmp)))

answer = []
for p in range(0, len(change), 2) :
    for q in range(p+1, len(change)+1, 2) :
        cal = change[0:p] + ['('] + change[p:q] + [')'] + change[q:]
        try :
            answer.append(eval(''.join(cal)))
        except :
            continue

print(min(answer))
        

이 코드에서 'leading zeros in decimal integer literals are not permitted; use an 0o prefix for octal integers' 에러가 발생했고, 에러의 의미는 10진수에서 0으로 시작하는 숫자 표기방법은 허가하지 않는다는 의미 라고 한다.
(출처 : https://www.codeit.kr/community/threads/10148)
반례는 예제의 '000009-000009' 였다.

• 틀린 코드 2

n = input()

tmp = ''
change = []
for i in n :
    if i.isdigit() :
        tmp += i
    else :
        if int(tmp) == 0 :
            change.append('')
        else :
            change.append(str(int(tmp)))
        change.append(i)
        tmp = ''
if tmp != '' :
    change.append(str(int(tmp)))

print(change)

answer = []
for p in range(0, len(change), 2) :
    for q in range(p+1, len(change)+1, 2) :
        cal = change[0:p] + ['('] + change[p:q] + [')'] + change[q:]
        try :
            answer.append(eval(''.join(cal)))
            print(cal)
            print(answer)
        except :
            continue

print(min(answer))

이전 코드에서 발생한 문제는 나타나지 않았지만, 괄호가 한 쌍만 있다고 판단해서 풀었기 때문에 틀렸다.

반례 : 0-100+50-100+50-100
https://www.acmicpc.net/board/view/83184

반례는 괄호를 두 개 써서 0-(100+50)-(100+50)-100으로 풀어야 최소값이 나온다.

위 반례로 인해 알게된 부분은 어차피 최소값을 구하는 문제이므로 -가 나오면 그 뒤부터 모든 +부분을 괄호로 묶어주면 된다는 것이다.

2. -부터 괄호 묶기

• 맞는 코드

n = input()

tmp = ''
change = []
# 숫자와 연산 기호를 분리시켜 하나의 배열로 만들었다.
# str(int(tmp))로 앞이 0으로 시작하는 숫자를 모두 일반 자연수로 만들어 줌
for i in n :
    if i.isdigit() :
        tmp += i
    else :
        change.append(str(int(tmp)))
        change.append(i)
        tmp = ''
# 마지막 숫자를 넣어주는 부분
if tmp != '' :
    change.append(str(int(tmp)))

check = ''
answer = []
for p in range(len(change)) :
	# 숫자면 배열에 넣기
    if change[p].isdigit() :
        answer.append(change[p])
    else :
        # -가 나오면 괄호 시작
        if change[p] == '-' :
        	# -가 연속해서 나올 수 있으므로 '('가 있는 경우 닫아주고 다시 새로 '('를 넣는다.
            if '(' in answer :
                answer.append(')')
            answer.append(change[p])
            answer.append('(')
            check = 'open'
        # +는 그냥 넣어준다.
        else :
            answer.append(change[p])

#맨 마지막 숫자가 괄호로 묶여있을 수 있으므로 확인
if check != '' :
    answer.append(')')

# eval() 함수를 이용해서 계산
print(eval(''.join(answer)))

• eval() 함수
  실행 가능한 문자열을 인자로 받아 실행하는 함수
  참고 : https://itinformation.tistory.com/110