[Swift] 프로그래머스 월간 코드 챌린지 3 금과 은 운반하기

 

Problem

 

코딩테스트 연습 - 금과 은 운반하기

---

Solution

 

해당 문제는 이진탐색을 이용해서 풀어야 하는 문제입니다.

 

최대로 걸릴 시간을 반으로 나눠가면서 금과 은을 운반할 수 있는지를 확인하는 것이 핵심입니다.

 

1. 최대로 걸릴 시간을 구한다.

 

아래 제한사항을 참고하면 a와 b의 최대치가 각 각 10의 9승이므로  10의 9승 * 2

 

움직이는데 최대로 걸리는 시간이 10의 5승이고 왔다 갔다 왕복이므로 10의 5승 *2

 

즉, 10e9 * 10e5 * 4입니다.

 

 

2. 이진 탐색을 이용하여 반으로 나누면서 광물을 운반할 수 있는지 확인한다.

 

광물을 운반할 수 있는지를 확인하는 방법은 모든 트럭의 광물의 합의 최대치가 모두

 

a(필요한 금의 양),b(필요한 은의 양),a+b(필요한 금과 은의 합)보다 크면 됩니다. (여기 해설에서 자세한 설명이 나와있습니다.)

 

각 트럭의 광물의 양과 (시간 내에 운반할 수 있는 횟수 * 무게의양 )을 비교해서 더 작은 쪽이 최대치가 됩니다.

 

이렇게 이진 탐색을 이용해서 광물을 운반할 수 없을 때까지 반복합니다.

---

Source Code

 

---

1차 풀이

 

첫 풀이는 아래와 같이 시간을 1초부터 세면서 원하는 결과 값이 되었을 때 리턴하도록 했다.

 

결과는...하나 뺴고 실패 (signal: illegal instruction (core dumped)) 라고 떴다... 

 

뭐... 시간초과가 걸리는 것도 아니고 다 위와 같은 오류가 떠서 당황했다..

 

import Foundation

struct Truck {
    var gold:Int
    var silver:Int
    var weight:Int
    var time:Int64
}

func solution(_ a:Int, _ b:Int, _ g:[Int], _ s:[Int], _ w:[Int], _ t:[Int]) -> Int64 {
    
    var gold:Int = a
    var silver:Int = b
    var time:Int64 = 0
    var waitingTrucks:[Int64:[Truck]] = [:]
    
    for (i,time) in t.enumerated() {
        if waitingTrucks[Int64(time)] == nil {
            waitingTrucks[Int64(t[i])] = [Truck(gold: g[i], silver: s[i], weight: w[i], time: Int64(t[i]))]
        }else {
            waitingTrucks[Int64(time)]!.append(Truck(gold: g[i], silver: s[i], weight: w[i], time: Int64(t[i])))
        }
    }
        
    while true {
        time += 1
        if waitingTrucks[time] != nil {
            for truck in waitingTrucks[time]! {
                var newTruck:Truck = truck
                var weight:Int = truck.weight
                if gold > 0 {
                    gold -= truck.gold > 0 ? truck.gold > weight ? weight : truck.gold : 0
                    if truck.gold > 0 {
                        weight = gold < 0 ? weight + gold : weight - truck.gold
                    }
                    newTruck.gold -= weight
                    gold = gold < 0 ? 0 : gold
                }
                if weight > 0 {
                    silver -= truck.silver > 0 ? truck.silver > weight ? weight : truck.silver : 0
                    newTruck.silver -= weight
                }
                if waitingTrucks[time + truck.time*2] == nil {
                    waitingTrucks[time + truck.time*2] = [newTruck]
                }else {
                    waitingTrucks[time + truck.time*2]!.append(newTruck)
                }
                if gold <= 0 && silver <= 0 {
                    return time
                }
            }
        }
    }
}

---

느낀점

 

이번 문제를 풀면서 먼저 식을 세우고 푸는 것이 중요하다고 느꼈다...

 

1차 풀이를 하고 도저히 어떤 방법으로 푸는지 모르겠어서 해설을 봤는데 이분탐색이라는 키워드가 있었다.

 

하지만 이분탐색이라는 키워드를 알고 나서도 금과 은을 운반하는 식 자체를 떠올리기가 힘들어서 나한테는

 

꽤 어려운 문제였다...

---

Reference

 

월간 코드 챌린지 시즌3 9월 해설