P42583. 다리를 지나는 트럭

https://programmers.co.kr/learn/courses/30/lessons/42583

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

 

소요 시간 약 40분

---

풀이.

스택을 이용해야하는 문제로 다리를 정해진 순서 대로 건널 때 최소시간을 구하는 문제이다.

아이디어는 loop 1회 일때 1초씩 행동하도록 로직을 구현하는 것

---

코드 1 - 기본적인 구현

    public static int solution(int bridge_length, int weight, int[] truck_weights) {
        int answer = 0;
        
        Queue<Integer> middle=new LinkedList<Integer>();
        Queue<Integer> end=new LinkedList<Integer>();
        
        for(int i=0;i<bridge_length;i++) {
        	middle.add(0);
        }
        
        
        int realWeight=0;
        int index=0;
        
        while(end.size()!=truck_weights.length) {
        	
        	//1초가 지나면 맨앞의 트럭을 제외함
        	if(middle.peek()!=0) {
        		realWeight-=middle.peek();
        		end.add(middle.poll());
        	}else {
        		middle.poll();
        	}
        	
        	//다리에 오르는 과정 
        	//다리가 견딜수 있는 무게 , 대기 트럭이 남아있으면  다리에 트럭을 올린다.
        	if(index<truck_weights.length && realWeight+truck_weights[index]<=weight) {
        		middle.add(truck_weights[index]);
        		realWeight+=truck_weights[index];
        		index+=1;
        	}
        	//아니면 0을 올림 
        	else {
        		middle.add(0);
        	}
        	
        	answer++;
        }
        
        
        
        
        
        return answer;
    }

코드 2 - 클래스를 이용한 구현

	static class Truck{
		int weight;
		int move;
		
		public Truck(int weight) {
			this.weight = weight;
			this.move = 1;
		}
		
		public void moving() {
			move++;
		}
		
	}
	
    public static int solution(int bridge_length, int weight, int[] truck_weights) {
        int answer = 0;
        
        Queue<Truck> wait=new LinkedList<Truck>();
        Queue<Truck> move=new LinkedList<Truck>();
        
        for(int i=0;i<truck_weights.length;i++) {
        	wait.add(new Truck(truck_weights[i]));
        }
        
        
        int realWeight=0;
        
        //대기 트럭이 있거나 다리위에 트럭이 있으면 계속 돔
        while(!wait.isEmpty() || !move.isEmpty()) {
        	answer++;
        	
        	//다리위가 비어있으면
        	if(move.isEmpty()) {
        		//대기 트럭에서 하나 뺌
        		Truck t= wait.poll();
        		realWeight+=t.weight;
        		move.add(t);
        		continue;
        	}
        	
        	//모든 트럭의 이동 위치를 +1 해준다. - linkedList기 때문에 모든 인덱스 접근이 가능
        	for(Truck t: move) {
        		t.moving();
        	}
        	
        	//제일 앞의 트럭의 인덱스가 다리의 길이를 벗어나면 = 도착지에 도착하면
        	if(move.peek().move>bridge_length) {
        		Truck t=move.poll();
        		realWeight-=t.weight;
        	}
        	
        	//대기트럭이 비어있지 않고, 현재 무게 + 다음트럭의 무게가 다리가 지탱할 수 있는 무게 일 경우에 
        	if(!wait.isEmpty() && realWeight + wait.peek().weight<=weight) {
        		Truck t=wait.poll();
        		realWeight+=t.weight;
        		move.add(t);
        		
        	}
        }
        return answer;
    }

 

---

실행 시간.

클래스를 이용한 풀이가 비교적 시간이 많이 걸리는 것을 확인할 수 있다.

 

코드 1

 

코드 2