GaGe

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

알고리즘/[2020] 프로그래머스

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

Sorrel 2020. 4. 13. 19:47
import java.util.Queue;
import java.util.LinkedList;
class Solution {
    class Truck { //트럭 각각의 무게와 입장시간을 기억하는 구조체(이 세트로 큐에 들어감)
        int weight;
        int start;
        
        Truck(int weight, int start){
            this.weight = weight;
            this.start = start;
        }
    }
    
    public int solution(int bridge_length, int weight, int[] truck_weights) {
        Queue<Truck> a = new LinkedList<>(); //Truck구조체로 설정
        Queue<Truck> b = new LinkedList<>();
        
        for(int i = 0 ; i < truck_weights.length ; ++i){ //waiting 큐에 트럭리스트 복사
            a.offer(new Truck(truck_weights[i], 0));
        }
        
        int time =0; //흐르는 시간 (실질적 정답)
        int total = 0; //bridge 위에 있는 total weight
        while(a.isEmpty()==false || b.isEmpty()==false){   
        	time++; //템포 당 일정하게 시간 흐르기
        	if(b.isEmpty()==false) { //브릿지에 트럭이 있다면
        		Truck t = b.peek(); //브릿지 맨 앞 큐원소
        		if(time - t.start >= bridge_length) { //브릿지 위에 머문 시간과 브릿지 길이 비교
        			total -= t.weight;
        			b.poll();
        		}
        	}
        	
        	if(a.isEmpty()==false) { //waiting큐에 트럭이 있다면
        		if(total+a.peek().weight <= weight) { //브릿지위의 weight+올라가려는 트럭의 weight와 감당 가능한 weigth 비교
        			Truck t = a.poll();
        			total += t.weight;
        			
        			b.offer(new Truck(t.weight, time)); //가능하면 브릿지에 올려줌
        		}
        	}
        }
        return time;
    }
}
Comments