[백준] [python] 1541

1541 잃어버린 괄호

시간제한: 2초

문제

세준이는 양수와 +, -, 그리고 괄호를 가지고 식을 만들었다. 그리고 나서 세준이는 괄호를 모두 지웠다.

그리고 나서 세준이는 괄호를 적절히 쳐서 이 식의 값을 최소로 만들려고 한다.

괄호를 적절히 쳐서 이 식의 값을 최소로 만드는 프로그램을 작성하시오.

입력

첫째 줄에 식이 주어진다. 식은 ‘0’~‘9’, ‘+’, 그리고 ‘-’만으로 이루어져 있고, 가장 처음과 마지막 문자는 숫자이다. 그리고 연속해서 두 개 이상의 연산자가 나타나지 않고, 5자리보다 많이 연속되는 숫자는 없다. 수는 0으로 시작할 수 있다. 입력으로 주어지는 식의 길이는 50보다 작거나 같다.

출력

첫째 줄에 정답을 출력한다.

예제1

# 입력
55-50+40
# 출력
-35

예제2

# 입력
10+20+30+40
# 출력
100

예제3

# 입력
00009-00009
# 출력
0

---

풀이 과정

문제 해석

주어진 식의 값을 최소로 만드는 방법을 찾는 문제이다.

사고 흐름

1. 임의의 괄호를 추가해서 최소값을 만드는 방법의 규칙을 찾아보았다.
2. 식이 -와 +만으로 이루어졌으므로 -연산을 할 때 최대한 많은 항을 같이 묶어 빼주어야 최소값을 만들 수 있을 것 같았다.
3. 식의 앞에서부터 계산을 해 나가다가 -연산이 존재하면 그 뒤에 나오는 -, +연산은 모두 -연산으로 대체 가능하다는 것을 발견했다.
   (ex. a + b - c + d + e - f $\rightarrow$ a + b - (c + d + e) - f)
4. 식의 앞에서부터 차례대로 계산을 하다가 -가 나오면 뒤의 수들을 모두 빼는 코드를 작성했다.

코드 작성

# 식을 -연산자를 기준으로 나누어 배열에 저장
exp = input().split('-')

# -연산을 하지 않는 앞 부분은 결과값에 미리 저장
# -가 나올때까지의 항들은 모두 더해주어야 하므로 sum 사용
# map 함수는 iterable 한 객체를 지정한 파라미터 대로 변환하여 다시 iterable 한 객체로 반환함.
# sum 함수는 list뿐만 아니라 iterable 한 객체를 더해주는 함수이므로 이 경우에 사용 가능하다.
res = sum(map(int, exp[0].split('+')))

# 최초로 나오는 -이후의 항은 모두 결과값에서 빼주기
# 위의 연산과 동일.
for i in exp[1:]:
    res -= sum(map(int, i.split('+')))
    
print(res)

---

처음에는 다음과 같은 코드를 작성했다.

exp = str(input())
res = 0

# 이전 정수를 임시로 저장하기 위한 배열
numArr = []

# 전에 -연산자가 나왔을 경우를 다루는 변수 선언
existMinusBefore = False

for i in exp:
	# 정수 처리
    if str.isdigit(i):
        numArr.append(i)
    # 연산자 처리
    else:
    	# 이전까지 나온 정수 형변환
        num = int(''.join(numArr))
        numArr = []
		
        # -연산자가 나왔는지 체크해서 정수의 연산 선택
        if existMinusBefore:
            res -= num
        else:
            res += num

        # 현재 -연산자가 나왔을 경우
        if i == '-': existMinusBefore = True
# 마지막 항 처리
if existMinusBefore:
    res -= int(''.join(numArr))
else:
    res += int(''.join(numArr))

print(res)

코드를 작성하고 보니 -연산자가 한 번만 나오면 뒤의 항들에서는 연산자가 의미가 없어진다는 것을 뒤늦게 깨달았고 연산자를 계속 체크하는 것이 비효율적이라고 느껴졌다. 또한 for문에서 전체 항을 처리하지 못하고 마지막 항을 따로 처리 해주는 것도 불편했다. 그래서 코드를 수정하였다.

---

총평

그리디 알고리즘과 관련된 문제를 풀 때에는 최대한 문제를 간소화시켜서 구현해보고 필요시 예외처리를 나중에 해주는 방식이 시간을 더 단축할 수 있을 것 같다는 생각이 들었다.