[백준] 13335번 트럭 (java, 구현)

www.acmicpc.net/problem/13335

13335번: 트럭

프로그래머스에도 있는 문제다 

일단 리스트에 트럭을 입력받는다는 생각에 list로 했지만 arraylist대신 queue를 쓰면 시간 효율성에 더 좋을 것이다

 

다리에 들어가는 트럭 리스트: Queue q 

다리에 들어가려고 기다리는 리스트: list

 

q혹은 list의 길이가 아직 1이 아니면 진행이 종료되지 않은 트럭이 있으므로 기다린다.

트럭이 빠져나오는 시간은 현재시간 + 다리길이로 넣어준다.

 

package algo0421;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

class Truck{
	int weight;
	int time;
	public Truck(int weight, int time) {
		super();
		this.weight = weight;
		this.time = time;
	}
	
}

public class B_1335_트럭_Main {
	static int n,len,weight;
	static ArrayList<Integer> list=new ArrayList<>();
	public static void main(String[] args) {
		Scanner sc=new Scanner(System.in);
		n=sc.nextInt();
		len=sc.nextInt();
		weight=sc.nextInt();
		
		for (int i = 0; i < n; i++) {
			int w=sc.nextInt();
			list.add(w);
		}
		
		int time=0;
		int sum=0;
		Queue<Truck> q=new LinkedList<Truck>();
		q.add(new Truck(list.get(0),time+len));
		sum+=list.get(0);
		list.remove(0);
		while(list.size()!=0 || q.size()!=0) {
//			System.out.println(time+"초, sum:"+sum);
			if(q.peek().time<=time) {
				Truck cur=q.poll();
				sum-=cur.weight;
			}
			if(list.size()>0 && sum+list.get(0)<=weight && q.size()<len) {//들어갈 수 있을 때
				q.add(new Truck(list.get(0),time+len));//무게, 나가는 시간
				sum+=list.get(0);
				list.remove(0);
//				System.out.println(sum);
			}
			time+=1;
		}
		System.out.println(time);
	}
}