ABOUT ME

-

Today
-
Yesterday
-
Total
-
  • 백준 16637 괄호 추가하기
    Algorithm/BOJ 2021. 3. 29. 12:03
    728x90

    출처: 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 까지 될 수 있다고 나와있는데...

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

    'Algorithm > BOJ' 카테고리의 다른 글

    백준 2210 숫자판 점프  (0) 2021.03.29
    백준 17406 배열 돌리기4  (0) 2021.03.29
    백준 17471 게리맨더링  (0) 2021.03.28
    백준 17136 색종이 붙이기  (0) 2021.03.28
    백준 1038 감소하는 수  (0) 2021.03.28

    댓글

Designed by Tistory.