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

 

 

• BOJ_1541.swift

• 1541 : 잃어버린 괄호/ 문제 소개
• 풀이 과정
• 코드 구현

https://www.acmicpc.net/problem/1541

1541번: 잃어버린 괄호

1541 :  잃어버린 괄호 / 문제 소개

 

그림1

세준이가 만든 식이다.

여기에 우리가 괄호 "( , ) "를 추가해서 이 식의 값을 최소로 만드는게 이 문제의 핵심이다.

문제에서 주어졌듯 첫번째와 마지막 문자는 숫자이다!! 즉 첫번째가 음수인 경우를 신경써 주지 않아도 된다.

 

연속해서 2개 이상의 연산자도 나타나지 않는다.

풀이 과정

 

어떻게 Greedy한 방식으로 주어진 식에 괄호를 한번~ 여러번 쳐서 식을 최소로 만들까?

고민끝에 나온 결론은 음수를 크게 만드는 것이다.

 

위 그림1 입력처럼

55 - 50 + 40에서

음수는 -50인데 우리는 괄호를 칠 수 있다.

55 - ( 50 + 40 ) 이렇게 괄호를 치면 음수가 -50 보다 더 크게 나온다.

 

그래서 난 우선 값을 입력받을 때 연산자가 " - " 타입인 것들로 문자열을 끊어서 str 배열에 저장을 했다.

 

예를들어

10 - 20 + 30 - 40 + 50 + 60 - 70 의 입력값이 있다면

str[0] = 10

str[1] = 20 + 30

str[2] = 40 + 50 + 60

str[3] = 70

 

이렇게 값을 분리 하기 위해 .split(separator: "-")를 사용해 일단 문자열로 받았다. 이렇게 할 경우 

첫 값은 무조건 양수이다. 따라서 두번째 , 세번째, 네번째 ... n -1 번째 str에 들어있는 문자열들은 다 - 로 계산하면 된다. split으로 -가 있는 앞에는 다 분리 시켰기 때문이다.

 이 계산을 전체 문장으로 다시 표현하면 

( 10 ) - ( 20 + 30 ) - ( 40 + 50 + 60 ) - ( 70 )

이렇게 된다. str 배열의 원소들은 괄호 속 문자열들이다.

 

그렇다면 이제 str[0]에 들은 첫번째 문자는 무조건 양수이므로 str[1] 부터 str[str.count -1 ]까지의 원소들은 

한개의 숫자만 있거나, 여러개의 숫자가 있을 것이다. 이때 여러개의 숫자가 있을 때는 split(separator: "+")를 사용하면 된다. 한개의 숫자가 있을 때는 분리가 split가 사용이 되지 않겠지만 여러개가 있을 때는 또 분리가 된다

분리된 배열들은 문자열이기 때문에 split(separator:"+").map{Int($0)!}으로 바꿔서 임시 변수에 더하거나

 

for i in 0..<str.count
    {
        var temp = str[i].split(separator: "+")
        temp.forEach
        {
            sumList[i] += Int($0)!
        }
    }

이런식으로 나중에 Int()로 바꿔서 해도된다.

 

코드 구현

 

import Foundation

func BOJ_1541()
{
    var str      = readLine()!.split(separator: "-")
    var sumList  = Array(repeating: 0, count: str.count)
    var answer   = 0
    for i in 0..<str.count
    {
        var temp = str[i].split(separator: "+")
        temp.forEach
        {
            sumList[i] += Int($0)!
        }
    }
    answer = sumList[0]
    for i in 1..<sumList.count
    {
        answer -= sumList[i]
    }
    print(answer)
}
BOJ_1541()

 

visit my github