졍's 기술 블로그

잃어버린 괄호

티어 : Silver 2
시간 제한 : 2 초
메모리 제한 : 128 MB
알고리즘 분류 : 수학, 문자열, 그리디 알고리즘, 파싱

문제

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

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

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

입력

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

출력

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

예제 입출력

Algorithm

1. 숫자는 숫자끼리, 연산자는 연산자끼리 각각 다른 List에 저장
    1.1. 숫자를 저장할 때 자릿수 생각해서 정수로 담기
2. A - B + C의 경우 - 연산자 뒤의 값 모두 계산하기
    2.1. - 연산자가 여러 개 있는 경우 A - B + C - D에서 A - (B+C) - D 로 계산

Code

# 입력
data = input()

operator_ = []
nums = []
temp = []
index = 0
for i in range(len(data)):
    if data[i] in ['+', '-']:
        operator_.append(data[i])
        # 숫자 자릿수에 맞춰서 하나의 숫자로 만들기
        nums.append(0)
        for j in range(len(temp)):
            nums[index] += temp[-1] * (10**j)
            del temp[-1]
        index += 1
    else:
        temp.append(int(data[i]))
# 마지막 숫자 추가
nums.append(0)
for j in range(len(temp)):
    nums[index] += temp[-1] * (10**j)
    del temp[-1]

# - 연산자 나오면 그 다음 - 연산자 전까지 + 모두 계산
i = 0
while True:

    # operator가 비어있으면 while문 돌지 않고 바로 출력
    if not operator_:
        break
    
    # - 연산자가 있으면 -연산자와 -연산자 사이의 값 모두 계산
    if operator_[i] == '-':
        
        index = 0
        flag = False # - 연산자 못찾으면 True
        
        if len(operator_) == 1 or i == len(operator_)-1:
            flag = True
            
        # 다음 - 연산자 찾기
        for j in range(i+2, len(operator_)+1):
            if operator_[j-1] == '-':
                index = j-1
                flag = False
                break
            else:
                flag = True
        
        # 그 뒤에 - 연산자가 없었다면
        if flag == True:
            nums[i+1] = sum(nums[i+1:])
            index = len(nums) - 1
        else: # - 연산자 있으면
            nums[i+1] = sum(nums[i+1:index+1])
        
        # 다음 - 연산자 전까지 모두 계산
        if '+' in  operator_[i+1:index]:
            temp = i + 2
            end = index + 1
            while True:
                nums[i + 2] = 0
                del operator_[i + 1]
                if nums[i + 2] == 0:
                    del nums[i + 2]
                    end -= 1
            
                if i + 2 == end:
                    break

    if i == len(operator_) - 1:
        break
    
    i += 1
    
for i in range(len(operator_)):
    if operator_[i] == '-':
        index = operator_.index('-')
        nums[index] -= nums[index+1]
        del nums[index+1]
print(sum(nums))

메모리: 30864 KB
시간: 76 ms