[백준] 1541번 : 잃어버린 괄호 (🥈실버 2) (Python)

문제 바로 가기

1541번: 잃어버린 괄호

 

---

풀이

• 사용 언어 : Python
• 풀이한 날짜 : 2024-01-11

 

input_str = input()
answer = 0

# 1st. 수식 문자열을 항으로 분류하여 리스트로 만듦
exp_lst = []

number = [i for i in range(10)]
number_temp = []
for elem in input_str:
    if elem in str(number):
        number_temp.append(elem)
    else:
        exp_lst.append(''.join(map(str, number_temp)))
        number_temp.clear()
        exp_lst.append(elem)
exp_lst.append(''.join(map(str, number_temp)))


# 2nd. 계산
minus_flag = False
temp_sum = 0

for idx, elem in enumerate(exp_lst):
    if idx == len(exp_lst) - 1:
        temp_sum += int(elem)
        if minus_flag == True:
            answer -= temp_sum
        else:
            answer += temp_sum

    if elem == '+':
        pass
    elif elem == '-':
        if minus_flag == False:
            minus_flag = True
            answer += temp_sum
        else:
            answer -= temp_sum
        temp_sum = 0
    else:
        temp_sum += int(elem)

print(answer)

 

풀이 로직

• 그리디 방식으로 문제를 해결하였다.
• 식의 값을 최소로 만들려면 - 바로 뒤에 괄호를 치고 다음 -가 나오기 전에 괄호를 닫으면 된다.
• 만일 -가 더 이상 나오지 않는다면 식의 마지막에서 괄호를 닫으면 된다.
• -가 처음 나오기 전까지는 +만 등장하므로, 모든 숫자를 더하고 이를 결과값에 그대로 할당한다.

 

문제 접근 과정 및 느낀점

사실 이 문제는 다른 사람의 풀이를 참고해서 풀었다. 혼자서 오랜 시간 고민했음에도 마땅히 뾰족한 수가 보이지 않았기 때문이다.

처음에 생각한 풀이는 수식을 스택을 써서 후위 표기법으로 바꾼 뒤 또다시 스택을 써서 식을 계산하는 방식이었다. 하지만 이 방식은 지나치게 복잡해보였고, 이를 일일이 구현할 자신이 별로 없었다.

이번 문제는 그저 하나의 경험이라 생각하고 '이렇게 풀 수도 있구나'하고 넘겨야 겠다.