[BOJ] 1541번 | 잃어버린 괄호 (Python3)

🔗문제 보러가기

1541번: 잃어버린 괄호

 

 

문제 설명

세준이는 양수와 +, -, 그리고 괄호를 가지고 식을 만들었다. 그리고 나서 세준이는 괄호를 모두 지웠다.
그리고 나서 세준이는 괄호를 적절히 쳐서 이 식의 값을 최소로 만들려고 한다.
괄호를 적절히 쳐서 이 식의 값을 최소로 만드는 프로그램을 작성하시오.

 

---

입력

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

 

---

출력

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

 

---

예제 입출력

 

---

풀이 전략

처음엔 +와 -만 있는 수식에서 괄호를 친다고 값이 달라지나?.. 라는 생각을 했었는데 분배 법칙을 이용하는 문제였습니다.

55 - 50 + 40  ->  50 -(50 + 40) = -35

풀이과정은 그리 어렵지 않으나, 문자열을 숫자로 파싱(parsing)하는 과정이 귀찮았습니다.

다른 사람들이 푼 코드들을 보니 List Comprehension을 이용해서 단 2줄만에 푼 사람도 있네요... (내 코드는...)

 

제 풀이는 다음과 같습니다.

• 우선 문자열을 숫자로 변환하여 리스트로 반환하는 함수, 최솟값을 구하는 함수 이렇게 두 가지로 나누기
• 문제 조건에 의해, 첫 번째 숫자는 무조건 양수
• 양수는 괄호 치는 의미가 없고, 음수가 나왔을 때 결정
  • 그 다음 숫자 또한 음수라면 분배 법칙을 할 경우, 오히려 숫자가 커지게 되므로 그대로 두기
  • 그 다음 숫자가 양수라면 분배 법칙을 적용하여 그 다음 숫자에 -1을 곱해주기
• 숫자의 맨 앞에 0이 올 수 있으므로, 이 부분을 검사하는 변수 또한 필요

 

---

소스 코드 및 결과

문자열을 숫자로 변환하는 ToNumber() 함수

def ToNumber(stringFormular):
    result = []
    strInt = ""
    preOperator = '+'
    isFirstZero = True
    
    for element in stringFormular:
        if element.isdigit():   # 숫자일 경우
           if element == '0' and isFirstZero:  # 제일 큰 자리수가 0일 경우
               continue
           strInt += element

           if isFirstZero:                     # '40'처럼 이후의 0이 생략되지 않도록
               isFirstZero = False
        
        else:                   # 부호일 경우
            data = int(strInt)
            if preOperator == '-':
                data *= -1
            preOperator = element
            isFirstZero = True
            result.append(data)
            strInt = ""
    
    # for 문이 끝나면 맨 마지막 숫자가 list에 추가되지 않으므로 추가 작업 시행
    data = int(strInt)
    if preOperator == '-':
        data *= -1
    preOperator = element
    result.append(data)
    return result

최솟값을 찾아주는 Solution() 함수

def Solution(operands):
    N = len(operands)
    _sum = 0
    
    for i in range(N - 1):
        if operands[i] < 0:         # 음수일 경우 그 다음 수를 확인
            if operands[i+1] >= 0:  # (- +)의 경우 수행
                operands[i+1] *= -1
        _sum += operands[i]
    
    _sum += operands[-1]            # 맨 마지막 숫자는 계산 안 됐으므로
    return _sum

__main__

expression = input()
operands = ToNumber(expression)
result = Solution(operands)
print(result)