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

 

문제분석

 

목표: 모든 트럭을 다리를 건널때 걸리는 시간구하기

 

특수조건:  다리는 일정한 무게(weight)만 견딜수있음.  다리를 건널때 길이당 1초씩 걸림.

 

 

문제를 들어가기전에 소제목으로 스택/큐가 있는것처럼,  스택/큐의 기본기를 강화시키기 좋은 문제라고 생각합니다.

 

 

스택은  FILO 으로 먼저 들어간게 제일 나중에 나오는 형식이고,

큐는 FIFO으로 먼저 들어간게 제일 먼저 나오는 형식을 가집니다.

 

제일 먼저 들어간 트럭이 제일 먼저 나오는 문제의 맥락상 Queue를 써야겟다고 판단했습니다.

 

 

Queue를 사용하되, 트럭이 들어가는 조건, 탈출하는 시간을 구할 필요가있습니다.

 

그 이유는,  1.트럭이 여러대 들어가다 다리가 무게를 못견디는 경우를 제외해야하며,

 

2.트럭이 탈출할때, 다리의 무게가 다시 트럭의 무게만큼 증가하기때문에  언제 탈출하는지도 알아야합니다.

 

따라서, 각 트럭이 탈출하는 시간을 저장해두는 int[] goal 배열 하나를 생성해둡시다.

 

트럭을 다리에 입장시킬때,  조건을   트럭무게 < 현재 다리의 무게 로 판단합시다.

 

트럭이 입장한다면, 현재 다리의 무게 -트럭무게 작업을한뒤, 

트럭이 나가게될 탈출 시간을 int[]goal  배열에 저장합니다.

 

1초에 여러 트럭이 입장할수는 없으니 While문으로 감싸주진 않습니다. 

 

시간이 지나다, Queue에 가장먼저 저장된 트럭의 탈출시간이 돌아오면, 

트럭을 빼준뒤에 다리 무게를 늘려줍니다.

 

이 모든 과정을마친뒤, Queue가 비어있다면 반복을 종료하고 현재시간을 반환합니다.

문제풀이

 

import java.util.*;
class Solution {
    public int solution(int bridge_length, int weight, int[] truck_weights) {
        int answer = 0;//현재시간
        // 모든트럭은 다리길이만큼 건너와야지 빠져나올수있다.
        // 즉, 트럭은 필연적으로 다리를 건너기시작하면 (현재시간+다리길이)시간때 무조건나오게댐 
        // 모든트럭이 지나가면 빠져나가도록 구현해보자.
        // goal은 각 트럭이 몇초에 도착할지를 체크한다. 
        int[] goal = new int[truck_weights.length];
        int i=0;
        Queue<Integer> que =new LinkedList<>();
        while(true){
            //트럭이 도착할때와 현재시각이 일치하면 트럭을 빼고, 무게를늘림
            if(!que.isEmpty()&&answer==goal[que.peek()]){
                weight+=truck_weights[que.poll()];            
            }
            //다리가 트럭을 견딜수있으면 트럭을 넣고 무게를 줄임
            if(i < truck_weights.length&&truck_weights[i]<=weight){
                weight-=truck_weights[i];
                que.offer(i);
                goal[i]=answer+bridge_length;
                i++;
            }
            answer++;
            if(que.isEmpty()){
                break;
            }
        }
        return answer;
    }
}