[Swift 알고리즘] 백준 2343 기타 레슨

안녕하세요 코코종입니다.

오늘도 이진탐색으로 돌아왔습니다~~

50%에서 런타임에러가 발생하는 바람에... 고생을 좀 했습니다 껄껄...

//
//  main.swift
//  BackJoon
//
//  Created by kokojong on 2023/04/27.
//

import Foundation
// 백준 2343 기타 레슨

let input = readLine()!.split(separator: " ").map { Int(String($0))! }
let n = input[0]
let m = input[1]

let arr = readLine()!.split(separator: " ").map { Int(String($0))! }
let maxV = arr.reduce(0, +)

func binarySearch(l: Int, r: Int) {
    var l = l
    var r = r
    
    while l < r {
        let mid = (l + r) / 2 // 블루레이의 크기
        
        var cnt = 0 // 블루레이의 갯수 (m과 같아야함)
        var sum = 0 // 하나의 블루레이에 들어간 크기 합
        
        for a in arr {
            if sum + a > mid { // 넘친다면
                sum = a // sum 초기화(새로운 것 넣어줌)
                cnt += 1 // cnt += 1
            } else {
                sum += a
            }
        }
        if sum > 0 { cnt += 1 } // 남은거 털기
        
        if cnt > m { // 크기를 너무 작게 잡은 경우 -> cnt가 많아짐
            l = mid + 1
        } else if cnt == m {
            r = mid // 혹시 더 작은 경우가 있나 찾기
        } else { // 크기를 너무 크게 잡은 경우 -> cnt가 적어짐
            r = mid
        }
    }
    
    print(r)
        
}

binarySearch(l: arr.max()!, r: maxV) // 제일 큰 크기보다 작은 조각으로는 쪼갤 수 없음, 다 더한것의 크기 이하여야함.

문제는 간단했는데요, 처음에 mid의 크기보다 작은 값이 들어올때에 대한 처리를 따로 해주다가 시간을 오래 잡아먹었습니다.

사실 생각해보면 arr에서 가장 큰 원소의 크기보다 작은 값으로는 나눌수 없는데 말이죠(이걸 또 백준이라고 생각하고 있던나...) 그래서 처음에는 범위를 0 ~ maxV*n 으로 생각했는데 범위를 다시 조정하게 되어서 arr.max ~ maxV로 조정했습니다.

 

그리고 sum과 cnt를 이용해 카운트를 하는 부분도 위와 같은 이유에서 조금 헷갈렸는데 범위 지정을 해주니 싹~ 해결되었습니다 (대충 개비스콘짤)

 

또 런타임 오류가 50%에서 계속 발생했는데 알고보니 원래는 mid == m일때 answers 배열에 추가를 해준뒤 가장 작은 값을 리턴하도록 구현했었는데 배열에 계속 추가해는 부분이 런타임 에러를 발생한 것 같더라구요..(그걸 빼니까 되네...) 아래와 같이 했다가 알수없는 런타임 오류에 빠져서 고생을 했답니다... append가 그렇게 하기 싫었나... 싶네요 허허...(아래에 첨부) 혹시 Swift로 푸는데 런타임 오류가 발생하신다면 참고해보세요~

if cnt > m { // 크기를 너무 작게 잡은 경우 -> cnt가 많아짐
            l = mid + 1
        } else if cnt == m {
            answers.append(mid)
            r = mid // 혹시 더 작은 경우가 있나 찾기
        } else { // 크기를 너무 크게 잡은 경우 -> cnt가 적어짐
            r = mid
        }
    }
    
    print(answers.min()!)