[백준] 잃어버린 괄호

문제

백준 잃어버린 괄호 https://www.acmicpc.net/problem/1541

 

코드

formular = list(input())
formular.append('-')

have_to_sum = []
have_to_sub = []
operand = ''

for letter in formular:
    if letter != '+' and letter != '-':
        operand += letter

    elif letter == '+':
        have_to_sum.append(int(operand))
        operand = ''

    elif letter == '-':
        have_to_sum.append(int(operand))
        have_to_sub.append(sum(have_to_sum))
        have_to_sum = []
        operand = ''

answer = have_to_sub[0]
for i in range(1, len(have_to_sub)):
    answer -= have_to_sub[i]

print(answer)

 

풀이

'-'를 기준으로 괄호를 치고, 나누어진 그룹별로 합을 구하고, 이 과정을 거친 각각의 숫자들을 빼주면 된다.

 

ex) 3 + 4 - 21 - 19 + 13 + 6 이라는 식이 있으면 다음과 같은 로직으로 제일 작은 수가 나온다.

3 + 4 - 21 - 19 + 13 + 6

➡️ (3,4), (21), (19, 13, 6) >> (3 + 4), (21), (19 + 13 + 6)

➡️ (7), (21), (38) >> 7 - 21 - 38

➡️ -52

 

formular = list(input())
formular.append('-')

입력 형식에 맞춰서 입력받고, 한글자 한글자 나누어서 formular 배열에 담는다.

'-' 기준으로 글자를 나눌것이기 때문에 배열의 마지막에 '-'를 추가한다.

 

have_to_sum = []
have_to_sub = []
operand = ''

have_to_sum 배열은 formular 배열을 '-'기준으로 나누었을때의 숫자들을 담는 배열이다.

have_to_sub 배열은 have_to_sum의 원소들의 합을 담는 배열이다.

operand 는 피연산자가 될 변수다. 예를들어 ['3', '3'] 을 operand 변수에 '33'으로 담는다.

 

for letter in formular:
    if letter != '+' and letter != '-':
        operand += letter

formular 배열에서 원소를 하나씩 가져온다.

가져온 원소가 숫자라면,

operand에 원소를 문자형태로 이어 붙인다.

 

elif letter == '+':
    have_to_sum.append(int(operand))
    operand = ''

가져온 원소가 '+'라면,

have_to_sum 배열에 operand를 정수형태로 바꿔서 넣는다.

operand는 빈 문자형으로 초기화 한다.

 

elif letter == '-':
    have_to_sum.append(int(operand))
    have_to_sub.append(sum(have_to_sum))
    have_to_sum = []
    operand = ''

가져온 원소가 '-'라면, 

have_to_sum 배열에 operand를 정수형태로 바꿔서 넣는다.

그리고 have_to_sum 배열에 쌓였던 정수형 원소들의 합을 have_to_sub 배열에 넣는다.

have_to_sum 과 operand는 비어있는 상태로 초기화 시킨다.

 

answer = have_to_sub[0]
for i in range(1, len(have_to_sub)):
    answer -= have_to_sub[i]

answer를 have_to_sub의 맨 처음 원소로 초기화 시키고, 

answer 에서 have_to_sub 원소의 인덱스 1부터 끝까지 뺀다.

 

다른 코드

formular = list(input().split('-'))
have_to_sub = []

for summ in formular:
    sum_result = sum(map(int, summ.split('+')))
    have_to_sub.append(sum_result)

answer = have_to_sub[0]
for i in range(1, len(have_to_sub)):
    answer -= have_to_sub[i]

print(answer)

 

풀이

결과값 도출의 전체적인 로직은 전 코드와 동일하다. 이 코드는 내장함수를 비교적 적극적으로 활용하였다.

formular = list(input().split('-'))
have_to_sub = []

입력받은 문자열을 '-'기준으로 나누어 배열화 한다.

ex) 3+4-21-19+13+6 ➡️ ['3+4', '21', '19+13+6']

 

for summ in formular:
    sum_result = sum(map(int, summ.split('+')))
    have_to_sub.append(sum_result)

sum_result는 formular 원소의 숫자 합이다.

have_to_sub 배열에 sum_result를 추가한다.

 

sum(map(int, summ.split('+')))을 더 자세히 살펴보자면

1. 가져온 원소(summ)을 '+' 기준으로 나누어서 ➡️ summ.split('+')

2. 생긴 조각들을 정수형으로 바꿔서 ➡️ map(int, summ.split('+'))

3. 모두 더한다 ➡️ sum(map(int, summ.split('+')))

 

answer = have_to_sub[0]
for i in range(1, len(have_to_sub)):
    answer -= have_to_sub[i]

answer를 have_to_sub의 맨 처음 원소로 초기화 시키고,

answer에서 have_to_sub 원소의 인덱스 1부터 끝까지 뺀다.

 

 

새롭게 배운점 / 느낀점

• a-b에서 b를 크게 하는 아이디어는 떠올랐지만, '-'기준으로 나눈다는 아이디어를 떠올리기 힘들어서 처음에 많이 헤맨 문제다.
• 그리디 알고리즘은 아이디어를 떠올릴 수 있는 능력을 요구한다. 그래서 그리디 해법은 그 정당성을 분석하는것이 중요하다.
• 그리디 문제는 아이디어를 떠올리는게 중요한것 같다. 이러한 능력을 기를려면 어떻게 해야할까?