-
백준 16637 괄호 추가하기Algorithm/BOJ 2021. 3. 29. 12:03728x90
출처: 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