백준 16637 괄호 추가하기

출처: www.acmicpc.net/problem/16637

분류: 완전탐색

---

접근방식

크게 두 부분을 이해하면 문제를 해결할 수 있습니다.

1. 괄호치기

2. 연산하기

 

---

 

0. 전처리

먼저 저는 괄호가 쳐질 연산자를 선택하는 방법을 이용할 것이기 때문에 전처리 작업에서 숫자와 연산자를 각각 배열에 분리해서 담아줬습니다.

for char in readLine()! {
    if char.isNumber {
        numbers.append(Int(String(char))!)
    } else {
        operators.append(char)
    }
}

 

1. 괄호치기

 

"괄호가 중복되지 않는다" , "괄호 안의 연산자는 1개" 라는 조건을 이용해서 해결했습니다.

위 조건을 생각해보면

괄호 안의 연산자는 오직 1개뿐이므로 연산자 중에서 괄호가 씌여질 연산자를 뽑을 수 있습니다 -> 조합

괄호가 중복되지 않기 때문에 괄호 연산자를 하나 뽑았으면 또 괄호 연산자가 올 수 없습니다. 

3 + 2 * 1 에서

+ 를 괄호 연산자로 뽑았다면 ( 3 + 2 ) * 1 

( ( 3 + 2 ) * 1 ) --> X 

그 다음의 연산자인 * 는 괄호가 될 수 없습니다.

따라서 조합을 뽑아줄 때 괄호를 뽑았다면 index + 2로 다음 연산을 건너띄워 주면 됩니다.

func selectBracket(_ idx: Int) {
    guard idx < hasBracket.count else {
        calcuate()
        return
    }
    
    hasBracket[idx] = true
    selectBracket(idx+2)
    hasBracket[idx] = false
    selectBracket(idx+1)
}

 

2. 연산하기

먼저 기본적으로 연산은 다음과 같이 진행했는데요,

연산자 배열을 operator,
연산자 배열의 인덱스를 op,
숫자가 담긴 배열을 num

이라고 하면 다음과 같이 연산합니다.

num[op+1] = operate( num[op], num[op+1], operator[op] )

num = [1, 2], operator = [*] 이면 
num[1] = 1 * 2 가 되는 것입니다.

 

 

이제 괄호쳐진 연산을 처리해야 하는데요, 제일 효율적인 방법인지는 모르겠으나 포문을 두 번 돌려주는 방식으로 연산을 했습니다.

먼저 첫 포문을 돌면서 괄호 연산자라면 두 수의 연산 결과를 앞에 넣어줬습니다.

num = [ 2, 2, 3, 4 ]
operator = [ *, +, * ]
bracket = [ false, true, false ] 일때 false는 건너뛰고 false를 연산해 앞에 넣습니다.

그럼 2 + 3을 먼저 계산에 2의 자리에 들어가므로 아래와 같이 됩니다.

num = [2, 5, 3, 4]
operator = [ *, +, * ]
bracket = [ false, true, false ] 

그리고 다음 포문을 돌면서 brack이
false면 정상적인 연산을 해주고
true라면 연산하지 않고 앞의 결과를 다음 인덱스에 저장만 해줍니다. 

연산 과정을 한번 살펴보면

num = [2, 10, 3, 4]
operator = [ *, +, * ]
bracket = [ false, true, false ] 

num = [2, 10, 10, 4]
operator = [ *, +, * ]
bracket = [ false, true, false ]    /// 연산하지 않고 앞의 값을 다음에 넘겨주기만 함

num = [2, 10, 10, 40]
operator = [ *, +, * ]
bracket = [ false, true, false ] 

이렇게 하고나면 맨 마지막에 최종적인 연산 결과가 남게됩니다 :)

func calcuate() {
    var operating = numbers
    
    for bracketIdx in hasBracket.indices where hasBracket[bracketIdx] {
        operating[bracketIdx] = operate(operating[bracketIdx], operating[bracketIdx+1], operators[bracketIdx])
    }
    
    for (idx, opr) in operators.enumerated() {
        operating[idx+1] = hasBracket[idx] ? operating[idx] : operate(operating[idx], operating[idx+1], opr)
    }
    
    if maxResult < operating.last! {
        maxResult = operating.last!
    }
}

 

 

해결방법

let n = Int(readLine()!)!
var numbers = [Int]()
var operators = [Character]()
var maxResult = Int.min

for char in readLine()! {
    if char.isNumber {
        numbers.append(Int(String(char))!)
    } else {
        operators.append(char)
    }
}

var hasBracket = [Bool](repeating: false, count: operators.count)
func selectBracket(_ idx: Int) {
    guard idx < hasBracket.count else {
        calcuate()
        return
    }
    
    hasBracket[idx] = true
    selectBracket(idx+2)
    hasBracket[idx] = false
    selectBracket(idx+1)
}

func operate(_ a: Int, _ b: Int, _ opr: Character) -> Int {
    switch opr {
        case "+": return a + b
        case "-": return a - b
        case "*": return a * b
        default: return 0
    }
}

func calcuate() {
    var operating = numbers
    
    for bracketIdx in hasBracket.indices where hasBracket[bracketIdx] {
        operating[bracketIdx] = operate(operating[bracketIdx], operating[bracketIdx+1], operators[bracketIdx])
    }
    
    for (idx, opr) in operators.enumerated() {
        operating[idx+1] = hasBracket[idx] ? operating[idx] : operate(operating[idx], operating[idx+1], opr)
    }
    
    if maxResult < operating.last! {
        maxResult = operating.last!
    }
}

selectBracket(0)
print(maxResult)

 

배운점

잘 풀어놓고 아무 생각없이 처음 최소값을 0으로 놓고 시작해서 틀렸다.

정답은 최소 2^-31 까지 될 수 있다고 나와있는데...

엄한 데서 또 시간을 한참 날렸다...