백준 1541 - 잃어버린 괄호 (파이썬)

문제

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

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

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

입력

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

출력

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

# 해결법

 

문제를 풀면서 간단한 방법이 있을 것 같았는데 생각이 안나서 억지로 풀어보았다. 

푼 방법은 문자열을 입력받고, 모두 나눠서 리스트화 한 다음, 문자열이 정수라면 number_list에 하나씩 더해줬다. 

예를 들어 '4', '0' 이 두 원소를 정수 '40'으로 만들어주기 위해 c = 0을 선언하고 연산자가 나오기 전까지 number_list [c]에 값을 더해주었다.

연산자가 나오면 리스트 인덱스를 1 더해주고 연산자를 넣고 인덱스를 다시 1 더해준다.

넘버 리스트를 거꾸로 내려오면서 + 연산자를 만나면 + 연산자 앞뒤의 원소들을 더하고 연산한 원소들을 모두 제거한다.

다시 넘버 리스트를 반복하면서 sum에 첫 원소를 넣고 - 연산자를 만나면 연산자 뒤의 값을 sum에서 빼준다.

마지막으로 sum을 출력해준다.

 

# 나의 코드

n = input() # 문자열 입력
n = list(n) # 문자열을 리스트화
int_list = ['0', '1', '2', '3', '4', '5', '6', '7', '8', '9'] # 정수 리스트
number_list = ['' for k in range(len(n))] # 빈 리스트 생성
c = 0 # 빈 리스트의 인덱스용 변수

for i in range(len(n)): # 문자열 길이만큼 반복
    if n[i] in int_list: # 원소가 정수라면
        number_list[c] += n[i] # 넘버 리스트에 문자열 형태로 더함
    else: # 원소가 연산자라면
        c += 1 # 넘버 리스트의 인덱스 +1
        number_list[c] += n[i] # 넘버리스트에 연산자 저장
        c += 1 # 넘버 리스트의 인덱스 +1

while '' in number_list: # 넘버 리스트에 공백이 있다면
    number_list.remove('') # 모두 제거

for l in range(len(number_list) - 1, -1, -1): # 넘버 리스트를 거꾸로 내려오면서
    if number_list[l] == '+':  # + 연산자를 만난다면
        number_list.insert(l - 1, ((int(number_list[l - 1])) + (int(number_list[l + 1])))) # + 연산자 앞뒤의 원소를 정수형으로 변환후 더하고
        del number_list[l] # 연산한 원소를
        del number_list[l] # 모두
        del number_list[l] # 제거해줌
sum = 0
for m in range(len(number_list)): # 넘버 리스트를 반복
    if m == 0:  # 처음에
        sum = int(number_list[0]) # sum에 첫 원소 값을 넣음  
    elif number_list[m] == '-': # - 연산자를 만나면
        sum -= int(number_list[m + 1]) # 연산자 뒤의 원소를 sum에서 빼줌
    else:
        continue
print(sum)

 

# 개선법

 

- 를 기준으로 split()하면 나오게 된 모든 원소를 첫 번째 원소에서 빼주면 된다.

예를 들어 50 - 50 + 50 - 50 - 50을 split()하면 ['50' , '50 + 50' , '50' , '50'] 이 되는데 첫 번째 50에서 나머지 원소들을 모두 빼주면 최솟값이 나오는 것이다.

첫 번째 원소에 +가 있을 경우 + 를 기준으로 split()하고 원소를 모두 더해준다.

두 번째 원소부터는 + 를 기준으로 모두 sum에서 반복해서 빼준다.

 

n = input().split('-')
sum = 0
for i in n[0].split('+'):
    sum += int(i)
for i in n[1:]:
    for j in i.split('+'):
        sum -= int(j)
print(sum)