[프로그래머스] 이분탐색 - 입국 심사 (Swift 풀이)

문제를 해결한 과정을 서술한 글입니다.

최종 풀이는 포스팅 맨 밑에서 확인하세요!

 

programmers.co.kr/learn/courses/30/lessons/43238#

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

 

얼마 전 쿠팡 캠퍼스 리크루팅 코딩테스트를 봤었다. 2번 문제가 가장 어려웠는데 이 문제와 굉장히 비슷했다!

대기 손님이 있고, 가장 빨리 끝나는 자리를 찾아 순차적으로 배정하는 문제였다.

쿠팡 테스트에서 풀었던 방식처럼 풀었는데 웬걸,,,, 시간 초과남........

큰일이다. 쿠팡 문제도 그냥 테스트 케이스 통과하길래 제출했는데 비효율 끝판왕으로 풀었던 것 같다ㅠㅠ

이진 탐색으로 풀어야 하는 문제구나, 다 풀고나서야 느꼈다.

 

문제를 풀어나간 과정

-> 반복문 노가다로 풀기

-> 조금 다른 접근 방법으로 반복문으로 풀기

-> 이진탐색 도입하기

-> 최소값임을 확인하고 반환하기

-> 1분 차이동안 완료되는 사람의 수가 여러명일 수 있음을 고려하기

 

반복문 노가다로 구하기1

일단 가장 먼저 풀었던 방식은,

비어있는 심사대가 있는 경우와 꽉 찬 경우를 따로 구분하지 않고 그냥 무조건 예상 종료 시간이 빠른 심사대로 가는 것으로 생각했다.

반복문을 돌려서 전체 심사대 중 가장 시간이 적게 남은 심사대를 선택하는 식으로 구현했다.

여기서 주의할 점은 소요시간이 1분 이상 1,000,000,000분 이하이므로 Int64 타입으로 반환해 주어야 한다는 것이다.

단순히 반환값만 Int64로 변환하여 반환하는 것이 아니라, 계산 과정에서도 Int64로 계산해야한다.

 

완성된 전체 코드(1차)

* 실행할 때는 print() 문을 제거해주어야 한다.

import Foundation

func solution(_ n:Int, _ times:[Int]) -> Int64 {
    var willDone: [Int64] = times.map {Int64($0)}
    var total: Int64 = 0
    
    for _ in 0..<n {
        // 가장 빨리 끝날 심사대를 찾는다
        var min: Int64 = willDone[0]
        var minIdx = 0
        for i in 1..<willDone.count {
            if min > willDone[i] {
                min = willDone[i]
                minIdx = i
            }
        }
        
        // 선택한 심사대의 예상 종료 시간을 업데이트 해준다.
        total = min
        willDone[minIdx] += Int64(times[minIdx])
        // print("\(minIdx)에서 심사, \(times[minIdx])소요, 현재까지 \(total)")
    }
    
    return total
}

테스트 케이스는 물론 완벽하게 통과하지만,, 사실 n이 최대 1,000,000,000까지 가능하고, times도 최대 길이가 100,000이므로

최악의 경우 반복문이 1,000,000,000,000,000돌게 된다... 말이 안되는 수치다.

당연히 실행해보면 모조리 시간초과가 뜬다.

 

 

반복문 노가다로 구하기2

비슷한 방법으로 조금 더 효율적으로 (보이게) 풀어보았다.

모든 사람이 입국심사를 끝내는 최소 시간을 구하는 문제이므로, 답은 항상 times 배열안의 값 중 하나의 배수로 끝난다.

그래서 모든 times 값에 1부터 n까지 곱하여 모든 배수의 경우의 수를 배열에 넣어보았다.

그리고 오름차순으로 정렬한 뒤, n번째 값을 찾는 방식으로 풀어보았다.

 

완성된 전체 코드(2차)

* 실행할 때는 print() 문을 제거해주어야 한다.

import Foundation

func solution(_ n:Int, _ times:[Int]) -> Int64 {
    var temp: [Int64] = []
    
    for i in 1...n {
        temp.append(contentsOf: times.map{Int64($0*i)})
    }
    temp.sort()
    // print(temp)
    
    return temp[n-1]
}

이 방법을 생각해 내고 진짜 아이디어 좋았다고 생각했다...ㅋㅋㅋ

하지만 따지고 보니 아까 풀었던 방식과 시간복잡도는 똑같았다.

오히려 항상 n번만큼 times의 모든 요소를 참조하므로 최악의 경우만 돌게되어 더 비효율적인 방법임을 깨달았다.

실제로 위에서 통과하던 3번 케이스도 더 오래 걸리는지 시간초과가 떴다.

 

 

이진탐색으로 접근하기

탐색 시간을 단축시키기 위해서, 이진 탐색 기법을 사용해보았다.

이진탐색은 정렬된 값의 전체 탐색 범위의 중간 값을 확인 한 뒤,

찾고자 하는 값이 크다면 중간값의 오른쪽, 작다면 왼쪽 범위만 탐색하는 식으로

탐색 범위를 반으로 줄여나가는 탐색 방식이다.

 

총 소요 '시간'을 탐색하는 문제이므로, 소요될 수 있는 최소 시간 ~ 최대 시간을 범위로 잡고 문제를 풀어나갔다.

최소시간은 1초, 최대 시간은 1,000,000,000분이다.

return binarySearch(start: 1, end: 1000000000)

 

binarySearch(start:, end:) 함수는 매개변수로 탐색 범위가 주어진다.

함수 내의 작동 방식은 다음과 같다

1. 탐색 범위의 중간값을 구한다.
2. 중간값에 해당하는 시간동안 총 몇명의 사람이 입국 심사대를 통과할 수 있는지 계산한다. => available(in:)
3. 계산한 값을 n과 비교한다.
   1. 계산한 값이 n과 같으면 해당 값을 반환한다.
   2. 계산한 값이 n보다 작으면 start부터 mid-1범위로 재귀 호출한다.
   3. 계산한 값이 n보다 크면 mid+1부터 end 범위로 재귀 호출한다.

func binarySearch(start: Int64, end: Int64) -> Int64 {
    let mid = (start+end)/2
    let sum = available(in: mid)
    
    if sum == n {
        return mid
    } else if sum > n {
        return binarySearch(start: start, end: mid-1)
    }
    return binarySearch(start: mid+1, end: end)
}

 

available(in:) 함수는 minute분 동안 총 몇명의 사람이 입국 심사대를 통과할 수 있는지 구하는 함수이다.

func available(in minute: Int64) -> Int64 {
    var sum: Int64 = 0
    for i in 0..<times.count {
        sum += minute/Int64(times[i])
    }
    return sum
}

 

완성된 전체 코드(3차)

* 실행할 때는 print() 문을 제거해주어야 한다.

import Foundation

func solution(_ n:Int, _ times:[Int]) -> Int64 {
    
    func binarySearch(start: Int64, end: Int64) -> Int64 {
        let mid = (start+end)/2
        let sum = available(in: mid)
        
        print(mid)
        if sum == n {
            return mid
        } else if sum > n {
            return binarySearch(start: start, end: mid-1)
        } else {
            return binarySearch(start: mid+1, end: end)
        }
    }
    func available(in minute: Int64) -> Int64 {
        var sum: Int64 = 0
        for i in 0..<times.count {
            sum += minute/Int64(times[i])
        }
        return sum
    }
    
    return binarySearch(start: 1, end: 1000000000)
}

 

최소임을 확인하고 반환하기

문제 접근 방식은 맞는 것 같은데 시간초과는 물론, 정답도 맞지 않는 케이스가 발생했다.

정답이 맞지 않는 이유는 최소 시간을 구하지 않고, n과 같은 값을 발견하면 바로 반환해버리기 때문에 발생한 문제였다.

 

n = 6, times = [7, 10] 인 경우는

1~1000000000 범위를 탐색하면 29분동안 6명을 완료할 수 있다는 결과가 나온다.

 

500000000분 -> 121428571명 완료
250000000분 -> 60714285명 완료
125000000분 -> 30357142명 완료
62500000분 -> 15178571명 완료
31250000분 -> 7589285명 완료
15625000분 -> 3794642명 완료
7812500분 -> 1897321명 완료
3906250분 -> 948660명 완료
1953125분 -> 474329명 완료
976562분 -> 237164명 완료
488281분 -> 118582명 완료
244140분 -> 59291명 완료
122070분 -> 29645명 완료
61035분 -> 14822명 완료
30517분 -> 7410명 완료
15258분 -> 3704명 완료
7629분 -> 1851명 완료
3814분 -> 925명 완료
1907분 -> 462명 완료
953분 -> 231명 완료
476분 -> 115명 완료
238분 -> 57명 완료
119분 -> 28명 완료
59분 -> 13명 완료
29분 -> 6명 완료 ----- return!!!!!

 

하지만 사실 28분만 지나면 6명을 완료할 수 있고, 29분에도 마찬가지로 6명이 유지가 된다.

따라서 최소값은 28이지만, 29에서 n과 같은 숫자가 나왔기 때문에 그대로 반환해버리는 문제였던 것이다.

 

그래서 mid분동안 몇명을 완료할 수 있는지 구한 다음

그 값이 n과 같으면 mid-1분동안 몇명을 완료할 수 있는지 한번 더 구해주었다.

만약 mid-1분동안 완료할 수 있는 사람이 n보다 작은 값이라면, 

mid-1분에서 mid 분으로 넘어가면서 n명을 처리할 수 있었던 것이기 때문에 mid를 바로 반환해 준다.! => 반환 조건 : 최소임을 확인하기

만약 mid-1분동안 똑같이 n명이라면, 그 앞의 범위에서 한번 더 탐색해주면 된다.

if sum == n {
    if available(in: mid-1) < n {
        return mid
    }
    return binarySearch(start: 0, end: mid-2)
}

 

완성된 전체 코드(4차)

* 실행할 때는 print() 문을 제거해주어야 한다.

import Foundation

func solution(_ n:Int, _ times:[Int]) -> Int64 {
    
    func binarySearch(start: Int64, end: Int64) -> Int64 {
        let mid = (start+end)/2
        let sum = available(in: mid)
        
        // print(mid)
        if sum == n {
            if available(in: mid-1) < n {
                return mid
            }
            return binarySearch(start: 0, end: mid-2)
        } else if sum > n {
            return binarySearch(start: 0, end: mid-1)
        } else {
            return binarySearch(start: mid+1, end: end)
        }
    }
    func available(in minute: Int64) -> Int64 {
        var sum: Int64 = 0
        for i in 0..<times.count {
            sum += minute/Int64(times[i])
        }
        return sum
    }
    
    return binarySearch(start: 1, end: 1000000000)
}

드디어 처음으로 4번 케이스까지 통과하였다. 하지만 여전히 시간초과가 뜨는 문제가 발생하였다.

이 방법으로 풀면 logN 시간이 소요되는데 (최악의 경우 = 30번만에 탐색 가능) 왜 통과되지 않을까 이해가 잘 되지 않았다..

 

 

1분 차이동안 완료되는 사람의 수가 여러명일 수 있음을 고려하기

사실 나는 '몇분동안 n명을 해결할 수 있는가'에만 집중해서 mid분동안 n명일 경우를 반환 조건으로 두었다.

하지만 예를들어, n = 3, times = [1, 1, 2] 일 경우 답은 2이다.

하지만 2분동안 총 5명이 완료, 1분동안 총 2명이 완료할 수 있으므로

내가 푼 방식으로는 영영 구할 수 없게 된다.

즉, 1분 사이에 완료될 수 있는 사람이 여러명이 될 수 있기 때문에 딱 n명으로 떨어지지 않는 경우가 생기는 것이다.

 

따라서

• mid분 동안 n명 이상이고, mid-1분동안 n명 미만이면 => mid 반환
• mid분 동안 n명 이상이고, mid-1분동안 n명 이상이면 => start ~ mid-1 탐색
• mid분 동안 n명 미만이고, mid+1분동안 n명 이상이면 -> mid+1 반환
• mid분 동안 n명 미만이고, mid+1분동안 n명 미만이면 -> mid+1 ~ end 탐색

이라는 조건을 도출할 수 있다.

 

그리고, 잘못된 입력이 들어오면 -1을 반환하도록 조건을 추가해주었다.

 

완성된 전체 코드(5차) - 최종 버전

* 실행할 때는 print() 문을 제거해주어야 한다.

import Foundation

func solution(_ n:Int, _ times:[Int]) -> Int64 {
    
    func binarySearch(start: Int64, end: Int64) -> Int64 {
        if start > end { return -1 } // 잘못된 입력이 들어오면 -1 반환
        
        let mid = (start+end)/2
        let midSum = available(in: mid)
        
        // midSum >= n 일 경우
        if midSum >= n {
            if available(in: mid-1) < n {
                return mid
            }
            return binarySearch(start: 0, end: mid-1)
        }
        
        // midSum < n 일 경우
        if available(in: mid+1) >= n {
            return mid+1
        }
        return binarySearch(start: mid+1, end: end)        
    }
    
    // minute분동안 입국심사를 완료할 수 있는 인원 수
    func available(in minute: Int64) -> Int64 {
        var sum: Int64 = 0
        for i in 0..<times.count {
            sum += minute/Int64(times[i])
        }
        return sum
    }
    
    let min = Int64(times.min()!)
    let max = Int64(n) * Int64(times.max()!)
    return binarySearch(start: min, end: max)
}