[Baekjoon]백준 1541 잃어버린 괄호(실버 2) - Python

문제설명

예제

문제를 살펴보면 주어진 식을 보고 적절한 위치에 괄호를 사용하여 최솟값을 만드는 문제이다

처음에는 문제를 잘못 이해하고 주어진 연산자와 숫자를 이용하여 최솟값을 만들면 되는줄 알았다

 

일단, 주어진 식을 적절히 분리하기 위해 for문과 isdigit()함수를 이용하여 연산자, 숫자를 따로 리스트에 저장하였다

그리고 마지막 for문 이후 숫자는 저장되지 않기 때문에 따로 if문을 추가하여 마지막 숫자를 저장해준다

이후에 sort()를 이용하여 밑의 사진처럼 숫자와 연산자를 각각 정렬해주고, 큰 수들을 더한 다음

작은수에서 큰 수들을 빼는 방식으로 코드를 작성하였다

formula = input()
number = []
operator = []
temp_num = ''

for char in formula: # 부호와 숫자 분리 
    if char.isdigit():
        temp_num += char
    else:
        if temp_num:
            number.append(int(temp_num))
            temp_num = ''
        operator.append(char)

if temp_num: # 마지막 숫자 추가
    number.append(int(temp_num))

number.sort(reverse=True)
operator.sort()
result = number[0]
# print(number)
# print(operator)
for i in range(len(operator)):
    if operator[i] == '+':
        result += number[i + 1]
    elif operator[i] == '-':
        result = number[i + 1] - result
        
print(result)

출력해보니 첫번째 예제에서 -65가 나오길래 어..? 뭔가 잘못했네? 라는 걸 깨닫고 다시 문제를 읽어보니

괄호를 적절한 위치에 넣어야하고, 숫자나 연산자의 위치를 바꾸는 것은 허용되지 않는다

그래서 이번에는 어떠한 방법으로 계산해야하는지 생각해보다가 뺄셈이 나오면 그 다음 뺄셈이 나오기 전까지

뒤의 숫자들을 모두 더해주면 된다고 생각하였다 그렇게 하면 뺄셈을 수행할 때 최대한 큰 수를 뺄 수 있기 때문이다

이를 위하여 '-'연산자가 이전에 등장하였는지 저장하는 변수를 하나 선언해주고, 이를 이용하여 뺄셈과 덧셈을 결정하였다

또한 뺄셈 뒤에 등장하는 식을 저장하기 위해 임시 변수를 하나 만들어주어 55 - 50 + 40 과 같은 식일때

50 + 40을 저장하는 역할을 수행하였다

formula = input()
number = []
operator = []
temp_num = ''

for char in formula: # 부호와 숫자 분리 
    if char.isdigit():
        temp_num += char
    else:
        if temp_num:
            number.append(int(temp_num))
            temp_num = ''
        operator.append(char)

if temp_num: # 마지막 숫자 추가
    number.append(int(temp_num))

tmp = 0
result = number[0]
sub = False # '-' 연산자의 상태 저장
for i in range(len(operator)):
    if operator[i] == '-':
        if sub:
            result -= tmp
        else:
            result += tmp
        # '-' 연산자를 만나면 이후의 숫자를 모두 묶어서 뺄셈 연산 수행
        tmp = number[i+1] 
        sub = True
    else:
        if sub:
            tmp += number[i+1]
        else:
            result += number[i+1]
            
if sub: # 마지막 tmp 계산
    result -= tmp
    
print(result)