프로그래머스 Lv2 다리를 지나는 트럭(스택/큐) Java

문제 설명

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

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

 

 

##문제이해##

Queue.size()==bridge_length 로 잡혀있는 블로그를 봤는데 처음에는 이해가 안됬다.. 디버깅으로 마지막까지 돌려보고서 이해했다.

다리를 상징하는 Queue를 생성하고 다리하중 이하일 경우는 계속 해당 큐에다가 넣고, 아닐경우 0(임시값)을 넣어서 큐를 사이즈만큼 채우는 반복을 수행한다.

그리고 다른사람들이 문제에 대해서 설명을 요청하는곳에서 다리길이 1씩 통과한다는 전제가 필요하다는 걸 알았다..

 

##내 코드##

import java.util.*;

class Solution {

    static int truck=0;

    public int solution(int bridge_length, int weight, int[] truck_weights) {

        List<Integer> resultList = new ArrayList<Integer>();

Queue<Integer> q = new LinkedList<>(); //다리를 재현할 큐

Queue<Integer> truckList = new LinkedList<>(); //다리를 재현할 큐

int weightsum = 0;

int time = 0;

//모든 트럭을 담는다

for(int i :truck_weights) {

truckList.add(i);

}

//무한반복 다리를 표현함 모든 트럭이 지나갔을경우에 종료시킴.

while(!(resultList.size()==truck_weights.length)) {

//큐가 비었을때

if(q.isEmpty()) {

truck = truckList.poll();

q.add(truck); //다리에 트럭이 올라간다.

time++;//시간증가

weightsum+=truck; //다리하중 체크를 하기위해 합계에 넣는다.

}else if(q.size()==bridge_length) {

//모두 가득찼을경우(time이 마지막까지 추가가 다 되고 빈칸에 0이 다 들어온경우 큐가 가득 찬다.)

int result =q.poll();

//차가 다리를 통과했으니 무게 제거; 임시값(0)은 사이즈 체크를위해 넣지않는다.

if(result!=0) {

resultList.add(result);

}

weightsum-=result;

}else {

//무게를 비교해서 weightsum이 제한하중 이하일 경우 다음차를 넣고, 아닐경우 임시값(0)을 넣어서 size를 키운다.

if(!truckList.isEmpty() && weight>=truckList.peek()+weightsum) {

truck=truckList.poll();

q.add(truck);//현재 트럭을 큐에 넣는다.

weightsum+=truck;//제한하중체크를 위해 무게합산 수행

time++; //시간증가

}else {

//제한하중이 가득차서 다음 트럭이 올라 갈 수 없으면 임시값(0)을 넣어서 차를 q에서 내보낸다.

q.add(0);

time++;//시간증가 무한반복(큐 사이즈가 가득차서 다리를 통과할때까지)

}

}



}//while문 종료

time= time+1; //마지막 통과시 1초 지나감

return time;

    }

}

##참고한 코드 및 주소##

https://minhamina.tistory.com/241

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

 

해당 블로그에 설명이 잘 되어있다.. 그런데 종료가 되는부분들이 이해가 안되서 내 코드는 다리를 끝까지 통과하는 로직으로 변경하여 처리했다.

import java.util.*;



class Solution {

    public int solution(int bridge_length, int weight, int[] truck_weights) {

        Queue<Integer> queue = new LinkedList<>();

int sum = 0;

int time = 0;



for(int i = 0; i < truck_weights.length; i++) { // 향상된 for문을 쓰는게 좋을 것

int truck = truck_weights[i];



while(true) {

// 큐에 아무것도 없는 경우 = 어떠한 트럭도 다리위에 없음

if(queue.isEmpty()) {

queue.add(truck);

sum += truck;

time++; // 다리에 오를 때만 시간 추가

break;

} else if(queue.size() == bridge_length) { // 큐에 다리 길이만큼 트럭이 다 찬 경우

sum -= queue.poll();

} else  { // 다리 길이만큼 큐가 차지않았음

// weight 값을 넘지 않는 선에서 새로운 트럭을 다리에 올려줌

if(sum + truck <= weight) {

queue.add(truck);

sum += truck;

time++;

break;

} else {

// 넘는다면 0을 넣어 이미 큐에 있는 트럭이 다리를 건너게 만듬

queue.add(0);

time++;

}

}

}

}



        // 마지막 트럭에서 반복문이 끝나는데, 마지막 역시 다리 길이만큼 지나가야하기에 + 다리 길이

return time + bridge_length;

    }

}