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

문제 링크

코딩테스트 연습 - 다리를 지나는 트럭 | 프로그래머스 (programmers.co.kr)

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

 

문제 설명

트럭 여러 대가 정해진 순서에 따라 다리를 건넙니다. (스택, 큐를 사용하는 문제는 순서가 정해진 경우가 많다.)

다리는 weight 이하의 무게만 견딜 수 있고 그에 따라 트럭의 배차 간격을 조정해 주어야 합니다.

 

 

풀이

Queue<Integer> que = new LinkedList<>();
Queue<Integer> bridge = new LinkedList<>();

Queue 2개를 사용.

que1에는 트럭 무게들을 순차적으로 넣고, bridge 가 문제를 푸는데 사용할 큐입니다.

bridge 에는 que1 에서 순차적으로 가져온 트럭의 무게를 넣습니다.

bridge는 이름 그대로 '다리' 라고 생각하면 되겠습니다.

 

중요한 부분은 길이가 존재한다는 것입니다. 따라서  bridge 에 bridge_length 만큼 공간을 확보해야 됩니다. 

for(int i=0;i<bridge_length;i++){
    bridge.add(0);
}

 

따라서 birdge_length 만큼 공간을 확보해줍니다.

0을 넣어주는 이유는,  bridge 에 있는 트럭의 무게들을 더할 때 영향이 가지 않게 하기 위함입니다. 

 

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

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]	[]	[]

위 표는 문제의 예시입니다.

다리를 건너는 트럭: [] 빈 공간에 0이 들어있다고 생각하면 됩니다. 

[7] 이나 [4] 처럼 하나의 숫자만 들어있는 곳에도 0이 생략되어 있는 것입니다.

[7 0] [0 7] [4 0] 이런 식으로요.

 

que1.front() + bridge 에 있는 트럭 무게들의 합 > weight  이라면

더 이상 다리에 트럭이 올라가지 못하므로,

bridge 를 오른쪽으로 한칸씩 전진해주면 되겠습니다.

 

bridge.poll();   bridge.add(0);   => 오른쪽으로 한칸씩 전진.

bridge 에 트럭이 추가로 들어가지 않는 경우 0을 더해줍니다.  0은 빈 공간이라고 생각하면 편합니다.

 

위처럼 que1 이 빌 때까지, 그리고 다리 위에 있는 트럭이 모두 전진하게 되면 종료입니다.

다리 위에 트럭이 없는지는 어떻게 처리할까요?

=> bridge 에 있는 무게의 합 = 0 이면 됩니다.

 

 

소스코드

public int solution(int bridge_length, int weight, int[] truck_weights) {
        int answer = 0;
        int truck_Num = truck_weights.length;

        Queue<Integer> que1 = new LinkedList<>();
        Queue<Integer> bridge = new LinkedList<>();

        int temp =0;  // bridge 에 있는 트럭 무게의 합
        for (int w : truck_weights) {
            que1.add(w);
        }
        for(int i=0;i<bridge_length;i++){
            bridge.add(0);
        }

        while(true){
            int front = 0;
            if(!que1.isEmpty())
                front = que1.peek();
            if(que1.isEmpty() && temp ==0) break;

            temp -= bridge.peek();
            bridge.poll();
            if(front + temp <= weight){
                bridge.add(front);
                temp+= front;
                que1.poll();
            }else
                bridge.add(0);
            answer+=1;
        }

        return answer;
    }