[Swift 알고리즘] 프로그래머스 lv3 - 입국심사

안녕하세요 코종입니다!

1일 1알고리즘이었는데 면접이다 뭐다 준비하느라..ㅎ 스킵이 되었던 날이 있네여

그래도 다시 시작합니다!

 

https://programmers.co.kr/learn/courses/30/lessons/43238

코딩테스트 연습 - 입국심사

import Foundation

func solution(_ n:Int, _ times:[Int]) -> Int64 {
    
    var left =  1
    var right = times.max()! * n  // 가장 오래 걸리는 경우 - 가장 오래걸리는데 n명
    
    while left != right {
        var mid: Int = (left + right) / 2 // 임시의 시간
        var person: Int = 0 // 이 시간 내에 가능한 인원
        
        for t in times {
            person += mid / t // 가능 인원을 계산
        }
        
        if person >= n { // 가능하다면 -> 시간이 남는걸지도? -> right 내림
            right = mid
        } else { // 가능한 인원이 적다면 -> 시간이 적었다 -> left 올림
            left = mid+1
        }
        
    }
    
    return Int64(left)
}

 

---

 

처음에는 1부터(1은 너무 심했나..?) 시간을 1씩 올려가면서 가능한 시간이라면 return을 하는 방식으로 생각했는데요.

그렇게 되면 최악의 경우 모든 경우를 다 돌아야 하기 때문에 시간이 엄청 오래걸리더라구요.. (처음에는 그 생각을 못 함)

그래서 문제 카테고리인 이진탐색으로 풀게 되었습니다. 최대, 최소를 계속 조절해가며 적절한 시간을 찾는 방식이었는데요, 가능한 인원을 처음에 어떻게 계산해야하나 고민했는데 문제를 보고 찬찬히 생각해보니 생각보다 간단했습니다 ㅎㅎ