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

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

문제 링크

url : https://www.acmicpc.net/problem/1541

1541번: 잃어버린 괄호

 

🍒 문제 분석

식이 주어지면, 괄호를 적절히 쳐서, 이 식의 값을 최소로 만들면 된다.

가령 55-50+40 이 주어지면, 55 - (50 + 40) 으로 최솟값을 만들 수 있다.

수는 0으로 시작할 수 있고, 연산자는 + 와 - 밖에 없다고 한다.

🥑 코드

cal = input()
sign ='+'
signidx = 0
minus_num = 0
result = 0

for i in range(len(cal)+1):
    if i != len(cal) and cal[i] == '-':         # - 를 만났을 때
        if i != 0 :                             # 인덱스 0이 - 가 아니라면 앞에 양수가 있는것이므로
            result += int(cal[signidx:i])       # result에 앞의 양수를 더한다.
        signidx = i                             # - 의 위치를 기록

        while i < len(cal):                     # - 뒤의 모든 값들을 다 더하면 된다.
            i += 1                              # - 뒤의 값들 보고 싶으므로 i를 뒤로 한칸 옮긴다.

            # 참고로 파이썬은 or 비교 연산에서 앞에게 True면 뒤에것을 더이상 안읽는다. 그래서 index erro 안난다.
            if i == len(cal) or cal[i] == '-' or cal[i] =='+':  # 문자열의 끝에 오거나 또는 부호를 만나면
                minus_num += int(cal[signidx+1:i])              # 숫자를 찾아내 더한다. (부호 사이의 값이 숫자)
                signidx = i                                     # 다시 부호를 기록한다.
        break

    elif i == len(cal) or cal[i] == '+' :      # -를 만나기 전, +연산으로 이루어진 값들은 다 더해버린다.
        result += int(cal[signidx:i])
        signidx = i

result -= minus_num
print(result)

 

🍓 내 해결 과정

- 연산자를 발견하면, 그냥 그 뒤에 모든 값을 다 -로 묶어서 생각하면 된다.

가령 50 - 40 + 80 - 3 이면, 50 - (40 + 80 ) - 3 과 같이, 처음 나온 -를 기점으로 전부 다 음수 값으로 묶인다.

 

1. '-' 를 만났을 때, 만약 '-' 위치가 0 이 아니라면 앞에 양수가 있는 것이므로 result에 양수를 더한다.

 

2. while 반복문으로 들어가서, '-' 뒤의 값들을 이제 다 더해준다.

 

3. 부호와 부호 사이에 있으면, i가 len(cal) 까지 오면 cal[signalidx:i] 가 숫자라는 점을 이용한다.

 

4. i 가 len(ca) 까지 왔을 때, cal[i] 이 부호인지 판별하는 코드는 에러를 일으킨다.

 

5. 그러나 파이썬은 인터프리터 언어로, 조건문 앞에서 True로 결론나면 그냥 다음줄로 넘어가기 때문에,
조건문 앞쪽에 i == len(cal) 을 써줬다.

 

6. break으로 조건문을 아예 빠져나온다.

 

7. '-' 를 만나기 전의 값들을 '+' 로 더해진다.

 

8. +로 더해진 값과 -로 더해진 값을 서로 연산하면 끝

 

🌽 다른 사람 코드

e = [sum(map(int, x.split('+'))) for x in input().split('-')]
print(e[0]-sum(e[1:]))

1. - 를 기준으로 요소를 나누고

2. + 를 기준으로 한번 더 요소를 나눠

3. + 기준으로 나눠진 요소들을 다 더하고

4. - 를 기준으로 나뉜 요소에서, 0번째 요소 - 나머지 요소들의 합 을 하였다.

 

만약 +로만 이루어진 연산이라면, - 기준으로 요소를 나눴을 때 0번째 요소만 존재할 것이다.

 

🍉 깨달은 점 및 정리

 

문자열로 연산이 주어졌을 때,

각 연산을 기준으로 split() 을 한 접근이 매우 유효하다는 것을 알게 되었다.

 

이걸 개념적으로 어떻게 설명해야할지 모르겠는데

 

앞으로 +, - 등의 연산 문자열이 나오면, split을 한번 떠올리게 될 것 같다.