[Algorithm] 백준 - 16638번 괄호 추가하기2 (Swift)

2025. 3. 27. 09:12· → Problems
목차
  1. 🧐 문제
  2. ✨ 풀이
  3. 🧙 결과

🧐 문제

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

✨ 풀이

괄호, 곱하기, 그외 연산자 순으로 연산을 진행하면 되겠다라고 생각했다. 그리고 괄호는 중복되면 안되기 때문에 오른쪽부터 괄호를 씌우게 하지만 이전에 괄호가 있다면 무조건 한칸 건너띄게 괄호를 넣을 수 있게 했다.

let n = Int(readLine()!)!
let math = Array(readLine()!).map { String($0) }

var cap = Array(repeating: false, count: n)

/// ["숫자", "부호", "숫자"] 연산
func operation(_ array: [String]) -> String {
    let left = Int(array[0])!
    let right = Int(array[2])!

    switch array[1] {
    case "*": return String(left * right)
    case "+": return String(left + right)
    case "-": return String(left - right)
    default: return "error"
    }
}

/// 괄호 -> 곱셈 -> 나머지 순서대로 연산
func calculate() -> Int {
    var temp1 = [math[0]]

    /// 괄호
    for i in stride(from: 1, to: n, by: 2) {
        if cap[i-1] {
            let last = temp1.removeLast()
            temp1.append(operation([last] + Array(math[i...i+1])))
        } else {
            temp1.append(math[i])
            temp1.append(math[i+1])
        }
    }

    var temp2 = [temp1[0]]
    
    /// 곱셈
    for i in stride(from: 1, to: temp1.count, by: 2) {
        if temp1[i] == "*" {
            let last = temp2.removeLast()
            temp2.append(operation([last] + Array(temp1[i...i+1])))
        } else {
            temp2.append(temp1[i])
            temp2.append(temp1[i+1])
        }
    }

    var temp3 = [temp2[0]]

    /// 나머지 무조건 연산
    for i in stride(from: 1, to: temp2.count, by: 2) {
        let last = temp3.removeLast()
        temp3.append(operation([last] + Array(temp2[i...i+1])))
    }

    return Int(temp3[0])!
}

var answer = calculate()

/// 가능한 모든 괄호에서 계산, 곱셈에서는 괄호를 씌우지 않음
func dfs(index: Int) {
    for i in stride(from: index, to: n-1, by: 2) {
        if !cap[max(i-2, 0)] && math[i] != "*" {
            cap[i] = true
            answer = max(answer, calculate())
            dfs(index: i+2)
            cap[i] = false
        }
    }
}

dfs(index: 0)

print(answer)

🧙 결과

🎉~ 아주 효과적으로 통과한 것 같다.

'→ Problems' 카테고리의 다른 글

[Algorithm] 프로그래머스 - 뒤에 있는 큰 수  (0) 2025.04.06
[Algorithm] 백준 - 16639번 괄호 추가하기3  (0) 2025.03.28
[Algorithm] 백준 - 1700번 멀티탭 스케줄링 (Swift)  (0) 2025.03.25
[Algorithm] 프로그래머스 - 모음사전  (1) 2025.02.05
[Algorithm] 프로그래머스 - 타겟 넘버  (0) 2025.01.15
  1. 🧐 문제
  2. ✨ 풀이
  3. 🧙 결과
'→ Problems' 카테고리의 다른 글
  • [Algorithm] 프로그래머스 - 뒤에 있는 큰 수
  • [Algorithm] 백준 - 16639번 괄호 추가하기3
  • [Algorithm] 백준 - 1700번 멀티탭 스케줄링 (Swift)
  • [Algorithm] 프로그래머스 - 모음사전
Swift librarian
Swift librarian
Swift librarian
Swift Library
Swift librarian
전체
오늘
어제
  • 분류 전체보기 (231)
    • 📺 Programming (5)
    • → Architecture (2)
    • → Design Pattern (0)
    • → Computer Science (15)
    • ⚙️ Algorithm (0)
    • → 알고리즘 관련 (22)
    • → Problems (104)
    • 🚀 Project (0)
    • → 알쏭달쏭 (0)
    • → Shook (2)
    • → Solver (8)
    • → Taster (7)
    • → Outline (4)
    • → Pointer (2)
    • → Guesser (3)
    • 🦜 Swift (2)
    • → Swift Archive (12)
    • → Swift Study (12)
    • → Xcode (6)
    • 🧰 Framework (0)
    • → Foundation (1)
    • → UIKit (2)
    • → SwiftUI (3)
    • → CoreData (2)
    • → MapKit (1)
    • → CoreHaptic (1)
    • → User Notification (1)
    • → StoreKit (2)
    • 🏛️ Library (0)
    • → TCA (0)
    • 🐈‍⬛ Git (8)
    • → Git의 원리 (2)
    • → Git 심화 (1)
    • 📦 Other (1)
    • 👦🏻 Log (0)

최근 글

hELLO · Designed By 정상우.v4.2.2
Swift librarian
[Algorithm] 백준 - 16638번 괄호 추가하기2 (Swift)
상단으로

티스토리툴바

단축키

내 블로그

내 블로그 - 관리자 홈 전환
Q
Q
새 글 쓰기
W
W

블로그 게시글

글 수정 (권한 있는 경우)
E
E
댓글 영역으로 이동
C
C

모든 영역

이 페이지의 URL 복사
S
S
맨 위로 이동
T
T
티스토리 홈 이동
H
H
단축키 안내
Shift + /
⇧ + /

* 단축키는 한글/영문 대소문자로 이용 가능하며, 티스토리 기본 도메인에서만 동작합니다.