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

문제

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

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

 

풀이

 초 단위로 트럭과 다리의 상태를 써내려가다보면 어떻게 해야할지가 보인다. 

 

초	대기트럭	다리
0	7 4 5 6	_ _
1	4 5 6	7 _	현재 다리의 무게+다음트럭의 무게 <= 다리가 버틸 수 있는 무게  - 대기열에 있는 트럭을 다리에 놓는다
2	4 5 6	_7	다리에 있는 트럭의 위치를 1칸씩 이동한다 현재 다리의 무게+다음트럭의 무게 > 다리가 버틸 수 있는 무게  - continue
3	5 6	4 _	다리에 있는 트럭의 위치를 1칸씩 이동한다 현재 다리의 무게+다음트럭의 무게 <=다리가 버틸 수 있는 무게  - - 대기열에 있는 트럭을 다리에 놓는다
4	6	5 4	다리에 있는 트럭의 위치를 1칸씩 이동한다 현재 다리의 무게+다음트럭의 무게 <=다리가 버틸 수 있는 무게  - - 대기열에 있는 트럭을 다리에 놓는다
5	6	_ 5	다리에 있는 트럭의 위치를 1칸씩 이동한다 현재 다리의 무게+다음트럭의 무게 > 다리가 버틸 수 있는 무게  - continue
6		6 _	다리에 있는 트럭의 위치를 1칸씩 이동한다 현재 다리의 무게+다음트럭의 무게 <=다리가 버틸 수 있는 무게   - 대기열에 있는 트럭을 다리에 놓는다
7		_ 6	다리에 있는 트럭의 위치를 1칸씩 이동한다 다음 트럭이 없다  - continue

 위를 대기트럭이 없고 다리위에 트럭이 없을 때까지 반복하면 된다.

 

트럭은 순서대로 진행시키기때문에 Queue나 Stack을 이용해야한다는 게 바로 보였지만, 다리를 무엇으로 구현해야하는지가 헷갈렸다. LinkedList로 할 경우, 다리의 길이를 어떻게 구현해야할지 모르겠어서 그냥 int배열로 구현했다. 조금 비효율적인 것 같다. 

 

코드

import java.util.LinkedList;
import java.util.Queue;
class Solution {
    public int solution(int bridge_length, int weight, int[] truck_weights) {
        int second = 0;        
        Queue<Integer> trucks  = new LinkedList<>();    //트럭대기열
        int[] bridge = new int[bridge_length]; 			// 다리
        int currentBridgeWeight = 0;           			//현재 다리위에 있는 트럭의 무게
        
        
        for(int i = 0 ; i<truck_weights.length;i++){
            trucks.add(truck_weights[i]);
        }
        
        
        while(!trucks.isEmpty() || currentBridgeWeight!=0){
            //다리에 있는 트럭의 위치 +1
            currentBridgeWeight = 0;
            for(int i = bridge_length-2; i>=0; i--){
                bridge[i+1] = bridge[i];
                currentBridgeWeight += bridge[i+1];
            }
            bridge[0] =0;

            //대기열에 있는 트럭을 다리에 놓을 수 있는지 확인
            if(!trucks.isEmpty()){
                int nextTruck = trucks.peek();
                if((currentBridgeWeight+nextTruck)<=weight){
                    nextTruck = trucks.poll();
                    bridge[0] = nextTruck;
                    currentBridgeWeight +=nextTruck;
                }
            }
            //초 증가
            ++second;
        }
        
        return second;
    }
}