[백준] 1541번 잃어버린 괄호 [Swift]

문제 링크

1541번: 잃어버린 괄호

문제

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

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

 

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

입력

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

출력

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

문제 풀이

우선 이 문제에서 가장 최소 값을 가지기 위해 괄호를 해야하는 부분은 현재 -가 나온 뒤의 +로 연결된 모든 숫자들이다.

예를 들어 55-50+40에서 뺄셈을 할 때 다음 뺄셈기호를 만날때까지 있는 모든 +로 연결된 숫자는 괄호를 쳐줘야한다.

즉 55-(50+40)이 정답이다.

 

즉 이 문제에서 가장 중요한 문자는 - 이다.

 

문제에서 주어진 문자열을 한 글자씩 확인해나가며 조건을 확인하여 계산을 하면된다.

 

나는 이 문제에서 발생할 수 있는 조건을 다음과 같이 정의했다.

 

• 현재 확인한 문자가 숫자인 경우
  • 숫자를 임시 저장
• 현재 확인한 문자가 + 면서 - 가 한 번도 안 나온 경우
  • 예를 들어 55 + 40인 경우 -가 없기 때문에 모두 더한 값이 최소값이다. 따라서 괄호가 필요없다.
• 현재 확인한 문자가 + 면서 - 가 한 번이상 나온 경우
  • 예를 들어 55 - 40 + 50인 경우 +가 나왔을 때 -가 한 번이상 나왔으므로 55 - (40 + 50)이 최솟값이다. 즉 다음 -를 만날때 까지 +가 나오면 숫자들을 계속 더해준다.
• 현재 확인한 문자가 - 면서 - 가 한 번도 안 나온 경우
  • 예를 들어 55 - 40인 경우 -가 나왔을 때 -가 한 번도 안나왔으므로 55에서 40을 빼야하는 상황이다. 즉 괄호가 필요없다.
• 현재 확인한 문자가 - 면서 - 가 한 번이상 나온 경우
  • 예를 들어 55 - 40 - 50인 경우 -가 나왔을 때 마다 현재 숫자들을 계속 빼줘야한다. 즉 괄호가 필요없다.

• 현재 마지막 문자를 확인하고 있으며 -가 한 번도 안 나온 경우
  • 예를 들어 55 + 40 + 50인 경우 모두 더해줘야 하기 때문에 마지막 숫자도 결과에 더해주면 된다.

• 현재 마지막 문자를 확인하고 있으며 -가 한 번 이상 나온 경우
  • 어떠한 경우에도 -가 한 번 이상 나오면 현재 숫자는 빼줘야한다. 따라서 현재 숫자도 빼주고 만약 +로 연결된 숫자들을 더한 값이 있다면 그 값도 빼준다.

이러한 조건들을 모두 점검하여 문제를 풀면된다.

 

조건들이 조금 복잡하여 구현할 때 실수는 몇 번 했는데 그런 것 외에 크게 어려운 점은 없는 문제인 것 같다.

소스 코드

func solution() -> Int{
    let expression = readLine()!

    var result = 0
    var tempSum = 0
    var minusAppearMoreThanOnce = false
    var nowNum : String = ""
    for offset in 0..<expression.count{
        let nowChar = String(expression[expression.index(expression.startIndex, offsetBy: offset)])
        if nowChar == "+"{
            if !minusAppearMoreThanOnce {
                result += Int(nowNum) ?? 0
                result += tempSum
                nowNum = ""
                tempSum = 0
            } else if minusAppearMoreThanOnce{
                tempSum += Int(nowNum) ?? 0
                nowNum = ""
            }

        } else if nowChar == "-"{
            if !minusAppearMoreThanOnce {
                minusAppearMoreThanOnce = true
                result += Int(nowNum) ?? 0
                result += tempSum
                nowNum = ""
                tempSum = 0
            } else if minusAppearMoreThanOnce{
                result -= Int(nowNum) ?? 0
                result -= tempSum
                nowNum = ""
                tempSum = 0
            }
        } else {
            nowNum += nowChar
        }

        if offset == expression.count - 1{
            if !minusAppearMoreThanOnce{
                result += Int(nowNum) ?? 0
                result += tempSum
            } else if minusAppearMoreThanOnce {
                result -= Int(nowNum) ?? 0
                result -= tempSum
            }
        }
    }
    return result
}

print(solution())