[그리디] 백준 1541번 잃어버린 괄호

문제 요약

양수와 +, -, 괄호로 만들어진 식에서 괄호를 모두 지운다.

해당 식에서 괄호를 적절히 쳐서 최소로 만드는 프로그램을 작성하라.

백준 1541번 문제 바로가기

입력

첫 번째 줄에 식이 주어짐.

식은 '0'~'9', '+', '-' 만으로 이루어져 있고, 처음과 마지막 문자는 숫자

연속해서 두 개 이상의 연산자가 나타나지 않고, 5자리보다 많이 연속되는 숫자는 없음.

숫자는 0부터 시작할 수 있고, 식의 길이는 50보다 작거나 같음.

출력

첫째 줄에 정답 출력

입출력 예시

입력	출력
55-50+40	-35

코드

inputData = input()
number = result = flag = 0
array = []

# 입력받은 식에서 숫자와 문자를 분리하여 새로운 list(변수명 array)에 저장
for i in range(len(inputData)):
    if "0" <= inputData[i] <= "9":
        number = number * 10 + int(inputData[i])
    else:
        array.append(number)
        array.append(inputData[i])
        number = 0
    if i == len(inputData) - 1:
        array.append(number)

# array에 저장된 값에 순서대로 접근
for i in range(len(array)):
	# i가 "-"일 때, flag를 1로 변경하고 for문으로 다시 돌아감
    if array[i] == "-":
        flag = 1
        continue
    # flag가 0이고 i가 숫자이면, 결과에 숫자를 더함
    if flag == 0 and type(array[i]) == int:
        result += int(array[i])
    # flag가 1이고 i가 숫자이면, 결과에 숫자를 뺌
    elif flag == 1 and type(array[i]) == int:
        result -= int(array[i])
print(result)

 

피드백

간단하게 찾을 수 있는 패턴을 복잡하게 돌아가서 찾았다. 기본적인 것부터 적용해보는 습관을 들이자. 입력받은 식에서 문자와 숫자를 분리하여 저장하는 것도 바로 해결하지 못했다. 제대로 알지 못하고 있구나 생각하게 됨.

 

내가 찾은 패턴

• - 뒤에 오는 +는 모두 -로 계산
  5 - 1 + 3 + 3 == 5 - (1 + 3 + 3) == 5 - 1 - 3 - 3

문제도 간단하고 해결법도 간단해서 어렵지 않게 풀었다.

다른 사람 풀이 참고

expression = input()
# '-'를 기준으로 자른 식을 변수 pluses에 저장
pluses = expression.split('-')

accumulate = 0

# 0부터 pluses의 길이까지 순서대로 접근
for index in range(len(pluses)):
	# pluses[index] 값을 '+' 기준으로 자른 뒤, 잘린 숫자를 모두 더해 변수 num에 저장
    num = sum(list(map(int, pluses[index].split('+'))))

	# 첫 번째 값을 결과에 저장하고, 그 뒤로는 결과 값에서 뺀다.
    if index is 0:
        accumulate = num
    else:
        accumulate -= num

print(accumulate)

list 속 값을 가져와 원하는 문자 기준으로 자른 후, 모두 더하는 것을 한 줄로 가능하다는 것을 배움.

• '-'를 기준으로 자른 식을 저장하면, 그 자체로 괄호를 친 역할을 한다.

 

깨달은 것

• 제공되는 메소드를 잘 사용할 수 있도록 연습이 필요
  여기에서는 sum(list(map(int, 변수[i].split("문자"))))로 list의 i번째 값을 "문자" 기준으로 나눈 뒤, 모두 더할 수 있다.