[Algo Rhythm🕺💃] 프로그래머스 고득점 Kit 다리를 지나는 트럭

문제 설명

트럭 여러 대가 강을 가로지르는 일 차선 다리를 정해진 순으로 건너려 합니다. 모든 트럭이 다리를 건너려면 최소 몇 초가 걸리는지 알아내야 합니다. 트럭은 1초에 1만큼 움직이며, 다리 길이는 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 이하입니다.

 

나는 어떻게 풀었나

import java.util.Queue;
import java.util.LinkedList;

class Solution {
    public int solution(int bridge_length, int weight, int[] truck_weights) {
        Queue<Integer> waitingTrucks = new LinkedList<>();
        Queue<Integer> bridge = new LinkedList<>();
        
        int sec = 0;
        int totalWeight = 0;
        
        for(int t : truck_weights) { waitingTrucks.add(t); }
        for(int i = 0; i < bridge_length; i++) { bridge.add(0); }
        
        while(!waitingTrucks.isEmpty()) {
        	int b = bridge.remove();
        	if(isTruck(b)) {
        		totalWeight -= b;
        	}
        	
        	int truck = waitingTrucks.element();
        	
        	if(isPassable(totalWeight, truck, weight)) {
        		bridge.add(waitingTrucks.remove());
        		totalWeight += truck;
        	} 
        	else {
        		bridge.add(0);
        	}
        	
            sec++;
        }
        
        while(!bridge.isEmpty()) {
        	bridge.remove();
        	sec++;
        }
        
        return sec;
    }
    
    public boolean isPassable(int totalWeight, int truckWeight, int limit) {
        return (totalWeight + truckWeight <= limit);
    }
    
    public boolean isTruck(int t) {
        return (t > 0);
    }
}

 

나는 왜 저렇게 풀었나

문제를 읽고나자 큐를 사용해야 한다는 것을 알았다. 그래서 아래와 같은 알고리즘을 생각했다.

 

1. 대기 트럭들을 모두 큐(트럭 큐)에 넣는다.

2. 크기가 bridge_length인 큐(다리 큐)를 만들고 값을 모두 0으로 초기화한다.

3. 다리 위에 있는 트럭들의 무게 합을 나타내는 totalWeight를 0으로 초기화한다.

4. 모든 트럭이 다리를 건너는 최단 시간을 나타내는 sec를 0으로 초기화한다.

5. 트럭 큐가 빌 때까지 아래 과정을 반복한다.

   1. 트럭 하나를 peek한다.

   2. total_weight + 트럭의 무게가 weight보다 작거나 같으면(= 다리에 올라갈 수 있으면) 아래와 같이 동작한다.

      1. 다리큐를 deque한 뒤 트럭을 enque한다. 그리고 totalWeight를 더해준다. 이때 트럭이 deque되었으면(= 무게가 0보다 크면) 그 트럭의 무게를 totalWeight에서 빼준다.

   3. 만약 그렇지 않으면 아래와 같이 동작한다.

      1. 다리큐를 deque한 뒤 0을 enque한다. 이때 트럭이 deque되었으면(= 무게가 0보다 크면) 그 트럭의 무게를 totalWeight에서 빼준다.

6. 다리 큐가 빌 때까지 deque를 하면서 sec를 increment한다.

하지만 이 알고리즘으로 실행할 경우 아래와 같은 input에 대하여 8이 아닌 10이 return되었다.

 

bridge_length = 2, weight = 10, truck_weights = [7, 4, 5, 6]

 

원인을 분석해보니 내가 다리에 동시에 트럭 하나가 들어오고 빠지는 경우를 고려하지았았다는 것을 알았다. 그래서 아래와 같이 알고리즘을 수정했다.

 

1. 대기 트럭들을 모두 큐(트럭 큐)에 넣는다.

2. 크기가 bridge_length인 큐(다리 큐)를 만들고 값을 모두 0으로 초기화한다.

3. 다리 위에 있는 트럭들의 무게 합을 나타내는 totalWeight를 0으로 초기화한다.

4. 모든 트럭이 다리를 건너는 최단 시간을 나타내는 sec를 0으로 초기화한다.

5. 트럭 큐가 빌 때까지 아래 과정을 반복한다.

   1. 다리 큐를 deque한다. 이 때 트럭이 deque되었으면(= 무게가 0보다 크면) 그 트럭의 무게를 totalWeight에서 빼준다.

   2. 트럭 하나를 peek한다.

   3. totalweight + 트럭의 무게가 weight보다 작거나 같으면 (= 다리에 올라갈 수 있으면) 다리 큐에 트럭을 enque한다. 그리고 그 트럭의 무게를 totalWeight에 더해준다. 마지막으로 트럭큐에서 트럭 하나를 remove한다.

   4. 만약 그렇지 않으면 다리큐에 0을 enque한다.

6.  다리 큐가 빌 때까지deque하면서 sec를 increment한다.

나는 무엇을 배웠나

Queue와 LinkedList javadoc을 읽으면서 queue 사용법을 익혔다!

https://docs.oracle.com/javase/7/docs/api/java/util/Queue.html

https://docs.oracle.com/javase/7/docs/api/java/util/LinkedList.html