[프로그래머스] (스택/큐) 다리를 지나는 트럭 (Java)

프로그래머스 Level 2  다리를 지나는 트럭 (자바)

출처

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

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

 

 

 

문제

트럭 여러 대가 강을 가로지르는 일 차선 다리를 정해진 순으로 건너려 합니다. 모든 트럭이 다리를 건너려면 최소 몇 초가 걸리는지 알아내야 합니다. 트럭은 1초에 1만큼 움직이며, 다리 길이는 bridge_length이고 다리는 무게 weight까지 견딥니다.
※ 트럭이 다리에 완전히 오르지 않은 경우, 이 트럭의 무게는 고려하지 않습니다.

예를 들어, 길이가 2이고 10kg 무게를 견디는 다리가 있습니다. 무게가 [7, 4, 5, 6]kg인 트럭이 순서대로 최단 시간 안에 다리를 건너려면 다음과 같이 건너야 합니다.

 

예시

 

따라서, 모든 트럭이 다리를 지나려면 최소 8초가 걸립니다.

solution 함수의 매개변수로 다리 길이 bridge_length, 다리가 견딜 수 있는 무게 weight, 트럭별 무게 truck_weights가 주어집니다. 이때 모든 트럭이 다리를 건너려면 최소 몇 초가 걸리는지 return 하도록 solution 함수를 완성하세요.

 

 

 

제한사항

 

• bridge_length는 1 이상 10,000 이하입니다.
• weight는 1 이상 10,000 이하입니다.
• truck_weights의 길이는 1 이상 10,000 이하입니다.
• 모든 트럭의 무게는 1 이상 weight 이하입니다.

 

 

 

 

 

입출력 예

입출력 예

 

 

 

한 줄 요약

대기중인 트럭을 Queue로, 다리를 지나는 중인 트럭을 ArrayList로 사용한다.

Truck 클래스를 만들어 해당 트럭의 무게와 가야 할 거리를 담는다.

 

 

풀이 원리

1. 트럭이 다리를 다 지나갔을 때, 견딜수 있는 무게를 원상 복귀하고 트럭을 진행 중인 배열에서 제거한다.

if (!move.isEmpty() && move.get(0).distance <= 0) {
	curWeight += move.get(0).weight;
    move.remove(0);
}

2. 대기중인 트럭이 존재하고, 다리가 견딜 수 있는 무게일 때 진행 중 배열에 추가하고, 견딜 수 있는 무게에서 뺀다.

if (!wait.isEmpty() && curWeight - wait.peek().weight >= 0) {
	curWeight -= wait.peek().weight;
    move.add(wait.poll());
}

3. 1초 지날때마다 진행 중인 트럭의 남은 거리를 1씩 감소시킨다.

for (int i=0; i<move.size(); i++) {
	truck = move.get(i);
    truck.distance--;
}

 

 

 

내 코드

1. 해당 트럭의 무게와 거리를 담을 Truck 클래스를 생성한다.

2. 대기트럭은 Queue, 다리를 건너는 트럭은 ArrayList로 생성한다.

3. 대기중인 트럭에 Truck 객체를 생성해 무게와 거리를 담는다.

4. 다리가 견딜 수 있는 무게를 curWeight 변수에 담는다.

 

5. wait와 move가 비어있지 않을 때 반복문을 돌린다.

6. 트럭이 다리를 다 지나갔을 때, 견딜 수 있는 무게를 원상 복귀하고 트럭을 진행 중인 배열에서 제거한다.

7. 대기중인 트럭이 존재하고, 다리가 견딜 수 있는 무게일 때 진행 중 배열에 추가하고, 견딜 수 있는 무게에서 뺀다.

8. 1초 지날때마다 진행 중인 트럭의 남은 거리를 1씩 감소시킨다.

 

9. answer(시간)++ 한다.

import java.util.*;

class Solution {
    public int solution(int bridge_length, int weight, int[] truck_weights) {
        //시간
        int answer = 0;
        
        Truck truck = null;
        
         //대기 트럭
        Queue<Truck> wait = new LinkedList<Truck>();
        //진행중 트럭
        ArrayList<Truck> move = new ArrayList<Truck>();
        
        for (int i : truck_weights) {
            wait.add(new Truck(i, bridge_length));
        }
        
        //다리 현재 무게
        int curWeight = weight;
        
        while(!(wait.isEmpty() && move.isEmpty())) {
            
            //다리를 다 지나갔을 때 견딜수 있는 무게 더하고, 진행중에서 제거
            if (!move.isEmpty() && move.get(0).distance <= 0) {
                curWeight += move.get(0).weight;
                move.remove(0);
            }
            
            //대기중인 트럭이 존재하고, 견딜수 있는 무게일 때 -> 진행중에 추가, 무게 마이너스
            if (!wait.isEmpty() && curWeight - wait.peek().weight >= 0) {
                curWeight -= wait.peek().weight;
                move.add(wait.poll());
            }
            
            //1초마다 남은거리 1씩 감소
            for (int i=0; i<move.size(); i++) {
                truck = move.get(i);
                truck.distance--;
            }
            answer++;
        }
        
        return answer;
    }
}

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

 

 

고려할 점

1. Queue와 ArrayList를 사용해  대기 중, 지나가는 트럭을 구분하는 것

2. 각 경우의 수를 생각해 poll(), remove() 등을 사용하는 것

3. class를 만들어 데이터를 담아 객체로 사용하는 것