[프로그래머스] Swift - 금과 은 운반하기

https://school.programmers.co.kr/learn/courses/30/lessons/86053

프로그래머스

 

2024.01.04 기준 Level 3

 

알고리즘 공부를 위해 풀고 기록하는 글입니다!
참고만 해주시고 더 좋은 풀이법이 있다면 알려주세요!

 

아이디어

문제 조건

• 여러 도시가 존재 (도시의 개수 == g.count == s.count)
• 각 도시에 트럭이 1개씩 존재
• 각 트럭은 최대 w[i] kg 만큼의 광물을 한 번에 운반 가능
• 이 때 금과 은 동시에 운반 가능
  • a 도시에 금이 40kg, 은이 30kg이고 총 60kg을 운반할 수 있는 트럭이 있다면 금 40kg, 은 20kg를 운반하거나 금 30kg, 은 30kg를 운반하는 등 두 금속을 섞어서 운반할 수 있다는 의미입니다.
• 각 도시에서 목적지까지 편도로 이동하는데 t[i]시간이 소요
• 새 도시를 건설하기 위해 금 a kg과 은 b kg을 전달할 수 있는 가장 빠른 시간을 구하자

 

우선 문제 조건을 보면 a, b, g의 길이, s의 길이, w의 길이 등 여러 조건에서 최대 크기가 매우 큰 것을 확인할 수 있습니다. 따라서 모든 경우를 전부 완전 탐색하는 방법으로 풀면 시간 초과가 발생할 것이라고 추측할 수 있습니다.

 

이 문제에 대한 아이디어는 쉽게 떠오르지 않아 프로그래머스 질문하기 탭에서 도움을 받았는데 이 문제의 핵심 아이디어는

parametric search 입니다.

 

parametric search

• 주어진 문제를 결정 문제로 변형하여 이분 탐색을 통해 해결하는 것

 

이분 탐색이 핵심입니다. 이분 탐색을 활용하면 시간 복잡도를 대폭 낮출 수 있습니다. (logN)

그렇다면 이분 탐색의 대상이 중요한데 이 문제에서는 시간을 대상으로 삼아야 합니다.

 

즉, 시간 T가 주어졌을 때 새 도시를 건설 할 수 있는지를 검증하고 가능하다면 T의 범위를 축소하고 T를 하향 조정합니다. 만약 T 시간에 도시 건설이 불가능하다면 T를 상향 조정합니다.

 

while lo + 1 < hi {
    let mid = (lo + hi) / 2
    let possible = isPossible(time: mid, a, b, g, s, w, t)

    if possible {
        hi = mid
    } else {
        lo = mid
    }
}

 

이렇게 일반적인 이분 탐색의 형태를 사용하면 됩니다.

 

lo의 초기값은 0으로 하면 되고 hi의 초기값은 최악의 상황에서 도시를 건설하기 위한 시간으로 설정하면 됩니다.

 

문제 제한사항에 따라 a, b가 각각 10^9이고 t의 모든 원소 값이 10^5이고 w의 모든 원소 값이 1이며 g의 길이, s의 길이, w의 길이, t의 길이가 모두 10^5일 때가 최악의 상황입니다.

이 때 필요한 시간은

2 * (10^5) ➡️ 1회 운반 시 10^5 시간이 필요하고 왕복이기 때문에 2를 곱해 줌

2 * (10^9) ➡️ a와 b를 각각 1번씩 1kg 씩 운반하여 10^9kg을 채워야 함

이며,

이 두 값을 곱한 2 * (10^5) * 2 * (10^9) = 400000000000000 가 hi의 초기값이 됩니다.

 

 

 

이렇게 피룡한 시간의 범위를 축소해가며 이분 탐색을 진행합니다.

mid값인 시간에 대해 isPossible 함수를 통해 도시를 건설할 수 있는지 확인합니다.

 

isPossible에서는 주어진 시간 time 동안 각 트럭이 운반할 수 있는 최대 무게의 합을 구합니다. (total이라는 변수에 저장)

또한 각 트럭에서 주어진 시간 time 동안 운반할 수 있는 금과 은의 무게의 합을 구합니다. (totalGold, totalSilver라는 변수에 저장)

 

total >= (a+b) && totalGold >= a && totalSilver >= b 를 만족하면 time 시간에 새 도시를 건설 할 수 있음을 의미합니다.

 

풀이

1. isPossible 함수 구현

fileprivate func isPossible(time: Int, _ a:Int, _ b:Int, _ g:[Int], _ s:[Int], _ w:[Int], _ t:[Int]) -> Bool {
    var total = 0
    var totalGold = 0
    var totalSilver = 0
    
    for i in 0..<g.count {
        // i는 도시 번호이자 트럭 번호를 의미
        
        var cnt = time / (2*t[i]) // cnt: 옮길 수 있는 횟수
        
        if time % (2*t[i]) >= t[i] { // 마지막에 편도로 옮기는 것이 가능할 때를 처리
            cnt += 1
        }
        
        let weightsCanBeMoved = min(cnt*w[i], g[i]+s[i]) // time 동안 이 트럭이 옮길 수 있는 최대 무게
        total += weightsCanBeMoved
        
        totalGold += min(weightsCanBeMoved, g[i])
        totalSilver += min(weightsCanBeMoved, s[i])
    }
    
    return total >= (a+b) && totalGold >= a && totalSilver >= b
}

 

 

2. solution 함수 구현

fileprivate func solution(_ a:Int, _ b:Int, _ g:[Int], _ s:[Int], _ w:[Int], _ t:[Int]) -> Int64 {
    var lo = 0
    var hi = 400000000000000
    
    while lo + 1 < hi {
        let mid = (lo + hi) / 2
        let possible = isPossible(time: mid, a, b, g, s, w, t)

        if possible {
            hi = mid
        } else {
            lo = mid
        }
    }
    
    return Int64(hi)
}

 

이분 탐색을 활용한다.

 

이분 탐색의 종료 조건과 return 값을 lo 또는 hi 중 어떤 것으로 정할지 애매한 경우가 있는데 그럴 때는 이 링크를 참고하면 좋다!

 

 

 

마무리

parametric search에 대한 경험이 없으면 아이디어를 떠올리기 쉽지 않을 것 같다.

또한 isPossible 함수의 로직을 짤 때도 주어진 시간에서 도시 건설이 가능한지를 검사하는 조건을 정하는 것도 난이도가 높았다고 생각한다.

 

코드 자체는 간단하지만 아이디어를 생각하기 어려운 문제였습니다.