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

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

프로그래머스

코드

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

class Truck{
	int weight;
	int index;

	public Truck(int weight, int index) {
		this.weight = weight;
		this.index = index;
	}
}

class Solution {

	public static int solution(int bridge_length, int weight, int[] truck_weights) {
		int time = 0;

		// 기다리고 있는 트럭
		Queue<Integer> waitTruck = new LinkedList<Integer>();

		// 현재 다리 위를 건너고 있는 트럭
		List<Truck> workingTruck = new ArrayList<Truck>();

		// 트럭의 무게 넣어줌
		for(int t : truck_weights)
			waitTruck.add(t);

		// 다리위 트럭의 총 무게 - 초기값: 현재 다리위로 올라갈 트럭(peek)
		int totalWeight = waitTruck.peek();

		// 첫번째 트럭은 다리위로 바로 건너므로 넣어주기,
		workingTruck.add(new Truck(waitTruck.poll(), 0));

		// 모든 트럭이 다리를 건널때까지
		while(!workingTruck.isEmpty()) {
			time ++;

			// ★ 현재 다리위 트럭은 모두 한칸 씩 이동시킨다.
			for(int i=0; i<workingTruck.size(); i++) 
				workingTruck.get(i).index ++;

			// 다리를 모두 건넌 트럭은 빼준다.
			// 끝까지 갔으면 working에서 제외
			if(workingTruck.get(0).index > bridge_length) {
				totalWeight -= workingTruck.get(0).weight;
				workingTruck.remove(0);
			}

			// 다리위에 트럭을 더 올릴 수 있는 경우에는 대기에서 빼주고, working에 넣는다.
			if(!waitTruck.isEmpty() && totalWeight + waitTruck.peek() <= weight) {
				int nextTruck = waitTruck.poll();
				totalWeight += nextTruck;
				workingTruck.add(new Truck(nextTruck, 1));
			}
		}

		return time;
	}

풀이

큐 + 그리디 + 구현 (?) 정도의 문제 인 것 같다.

문제 풀때 이것저것 생각하느라 머리가 터지고,, 정답 코드 보며 이해하는데도 머리가 터진 문제다 ... 

처음엔 먼저 들어온 트럭이 먼저 나가는 순서여서 큐를 생각했고,

트럭이 들어올 때 마다 다리가 견딜 수 있는 무게와 비교해서, 다음 트럭도 비교해가며 무게와 견딜수 있는지 없는지

비교해가는식으로 판별해서 해결하려고 했으나 구현은 못하고 타 블로그를 참고했다.

https://taesan94.tistory.com/33

다른 풀이들을 봐도 이해가 안되서 나에게 그나마 이해가 가는 코드를 참조했고, 디버깅을 해보니 어느정도 이해가 갔다.

다시봐도 절대 못 풀 문제이기에 주말에 다시 복습하며 풀이를 올리겠다 . . .

 

 

 

 

2020.03.15 22:00 풀이

주어진 입출력에서 bridge_length = 2 , weight = 10 , truck_weights = [7, 4, 5, 6]을 기준으로 생각한다.

위 문제의 해결법은 다음과 같다.

모든 트럭이 다 건널때까지 1초씩 증가시키며, 문제의 조건에 맞게 구현한다.

클래스를 따로 생성해서 접근하는 방법도 알고리즘을 풀때는 거의 사용하지 않아서 더 어렵게 느꼈다.

 

Truck 클래스를 생성하는데, 이 트럭 객체는 트럭의 무게(문제에서 주어진 truck_weights)와

인덱스(트럭이 다리 위에서 위치를 나타냄)를 변수로 갖는 클래스다.

다리를 건너기 전의 트럭을 넣을 큐 waitTruck와 현재 다리를 건너고 있는 리스트 workingTruck

를 선언한다.

waitTruck 에는 현재 트럭의 무게를 넣어준다. 그럼 큐에는 7, 4, 5, 6 이 순서대로 저장된다.

모든 트럭이 다리를 건너야 하므로, 가장 첫번째 트럭의 무게를 리스트에 넣어준다.

다리 트럭의 총 무게도 각 트럭별로 비교해야하므로, 첫번째 트럭의 무게를 저장한다.

// 다리위 트럭의 총 무게 - 초기값: 현재 다리위로 올라갈 트럭(peek) int totalWeight = waitTruck.peek(); // 첫번째 트럭은 다리위로 바로 건너므로 넣어주기, 인덱스 = 0(첫번째) workingTruck.add(new Truck(waitTruck.poll(), 0));

 

 

그 후 모든 트럭이 다리를 건널때까지 - while(!workingTruck.isEmpty()) 1초마다 트럭을 이동하고, 모두 건넌 트럭이 있으면 제외하고, 트럭의 무게(totalWeight)와 다리가 견딜수 있는 무게(weight)를 비교하며 다리에 다음 트럭을 올릴지, 아닐지 비교한다.

 

트럭은 1초에 1만큼 움직이므로, 현재 다리위에 있는 트럭을 모두 한 칸씩 이동시킨다.

			for(int i=0; i<workingTruck.size(); i++) 
				workingTruck.get(i).index ++;

 

 

 

이동시킨후 만약 다리를 건넌 트럭이 있을경우  건넌 트럭의 무게를 빼고, 현재 리스트에서 제외한다.

			if(workingTruck.get(0).index > bridge_length) {
				totalWeight -= workingTruck.get(0).weight;
				workingTruck.remove(0);
			}

 

* 다리를 건넌 트럭이 있는지 확인은 리스트에 저장되어있는 트럭 객체의 인덱스와 다리의 길이를 비교하면 된다.

 

 

 

 

그 후 현재 통과하려는 트럭과, 다리에 있는 트럭을 비교하며 무게를 비교한다.

만약 다리위 트럭 + 현재 트럭의 무게를 더해도 다리가 견딜 수 있는 무게보다 작은경우(지탱가능한경우)

if(!waitTruck.isEmpty() && totalWeight + waitTruck.peek() <= weight)

 

트럭을 올리고, 현재 다리위에 있는 모든 트럭의 무게를 더해준다.

int nextTruck = waitTruck.poll();
totalWeight += nextTruck;

 

그 후 리스트에 현재 트럭 객체를 추가한다.

workingTruck.add(new Truck(nextTruck, 1));