[프로그래머스] 다리를 지나는 트럭 / Swift

[문제 보기]

트럭 여러 대가 강을 가로지르는 일차선 다리를 정해진 순으로 건너려 합니다. 모든 트럭이 다리를 건너려면 최소 몇 초가 걸리는지 알아내야 합니다. 다리에는 트럭이 최대 bridge_length대 올라갈 수 있으며, 다리는 weight 이하까지의 무게를 견딜 수 있습니다. 단, 다리에 완전히 오르지 않은 트럭의 무게는 무시합니다.

예를 들어, 트럭 2대가 올라갈 수 있고 무게를 10kg까지 견디는 다리가 있습니다. 무게가 [7, 4, 5, 6]kg인 트럭이 순서대로 최단 시간 안에 다리를 건너려면 다음과 같이 건너야 합니다.

 

경과 시간, 다리를 지난 트럭, 다리를 건너는 트럭, 대기 트럭

0	[]	[]	[7,4,5,6]
1~2	[]	[7]	[4,5,6]
3	[7]	[4]	[5,6]
4	[7]	[4,5]	[6]
5	[7,4]	[5]	[6]
6~7	[7,4,5]	[6]	[]
8	[7,4,5,6]	[]	[]

따라서, 모든 트럭이 다리를 지나려면 최소 8초가 걸립니다.

solution 함수의 매개변수로 다리에 올라갈 수 있는 트럭 수 bridge_length, 다리가 견딜 수 있는 무게 weight, 트럭 별 무게 truck_weights가 주어집니다. 이때 모든 트럭이 다리를 건너려면 최소 몇 초가 걸리는지 return 하도록 solution 함수를 완성하세요.

제한 조건

• bridge_length는 1 이상 10,000 이하입니다.
• weight는 1 이상 10,000 이하입니다.
• truck_weights의 길이는 1 이상 10,000 이하입니다.
• 모든 트럭의 무게는 1 이상 weight 이하입니다.

입출력 예

bridge_length, weight, truck_weights, return

2	10	[7,4,5,6]	8
100	100	[10]	101
100	100	[10,10,10,10,10,10,10,10,10,10]	110

 

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

코딩테스트 연습 - 다리를 지나는 트럭

 

---

처음에 프로그래머스에 있는 문제 설명이 이해가 가지않아서 문제 원본 설명을 보았다.

문제출처: http://icpckorea.org/2016/ONLINE/problem.pdf

 

다리를 건너는 트럭들

 

swift에서 큐 자료형이 따로 없어서 간단하게 가장 먼저 들어간 원소를 빼내야할 때는 배열 자료형의 removeFirst를 사용했었다. 이 방법의 단점은 O(1)에 수행되는게 아닌 O(n)이 걸리는 작업이라는 것이다.

 

이번 문제에서는 배열의 removeFirst를 사용하지 않고 한개의 배열과 first, last 인덱스만으로 다른 언어에서 제공되는 일반적인 큐처럼 removeFirst, append 작업을(O(1)) 사용해보았다. (선형 배열을 이용한 순차 큐)

 

사실 이 방법은 지속적으로 새로운 원소가 append, removeFirst가 될 때 사용하지 못하는 공간이 계속 커지게 되어 비효율적이지만, 이 문제의 조건에서는 주어지는 삽입/삭제 횟수가 1만개 내에서 해결되는 경우라서 이정도면 적당하다고 생각했다.

 

큐의 첫번째 원소의 인덱스를 가리키는 first는 큐가 비어있을 때는 0을 가리키게 한다.

큐의 마지막을 가리키는 last는 마지막 원소가 들어있는 인덱스의 그 다음 인덱스를 가리키게 한다.

따라서 처음에 큐를 만들 때도 전체 길이는 들어갈 큐의 길이 + 1만큼 잡아야 한다.

큐가 비었는지 아닌지는 first < last 로 비교, 비어있는게 아니라면(원소가 들어있으면) true, 아니라면(비어있다면) false가 나오는 것으로 확인한다. (first가 last와 같거나 더 크면 비어있는 상태) 

 

import Foundation

func solution(_ bridge_length:Int, _ weight:Int, _ truck_weights:[Int]) -> Int {

    func isQueueEmpty(_ first: Int, _ last: Int) -> Bool {
        return first < last ?  false : true
    }
    func appendQueue(_ element: (Int, Int)) {
        queue[last] = element
        last += 1
    }
    func popQueue() -> (Int, Int) {
        let element = queue[first]
        first += 1
        return element
    }
    func moveAllTruck() {
        for i in (first..<last) {
            let element = queue[i]
            queue[i] = (element.0, element.1 - 1)
        }
    }

    var time = 0, truckIndex = 0, first = 0, last = 0
    var queue = [(Int, Int)](repeating: (-1, -1), count: truck_weights.count + 1)
    var passed = 0 // 다리를 지난 트럭의 수
    var allWeight = 0
    while truckIndex < truck_weights.count { // 대기 트럭이 없어질 때까지
        let element = truck_weights[truckIndex]
        if allWeight + element <= weight { // 아직 더 건널 수 있을 때
            appendQueue((element, bridge_length - 1))
            allWeight += element // 다리에 걸리는 무게 갱신
            truckIndex += 1   
        }   

        moveAllTruck()
        time += 1
        // print(time)
        if queue[first].1 < 0 { // 맨 앞의 트럭이 나왔을 때
            let truck = popQueue()
            allWeight -= truck.0
            passed += 1 // 다리를 건넌 트럭의 수를 추가
        }
    }    
    time = time + (queue[last - 1].1 + 2) // 큐에 남은 트럭들 중 마지막 트럭의 건너는 시간을 더함

    return time
}

---

생각 정리

다른 사람 풀이를 보니 트럭을 넣기전에 먼저 다리에 공간이 남아있는지 아닌지 확인하는 방법도 있었다.

 

 

큐 구현에 대해서 정리해야겠다.

1. 스택 2개로 큐 만들기

2. 원형 큐