[프로그래머스 / Java] 코딩테스트 연습: 다리를 지나는 트럭 (스택 / 큐)

난이도: Level 2

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

프로그래머스

---

 

이 문제의 지문은 확실히 잘못 되었다.

트럭이 다리를 모두 지나기까지의 경과 시간이 어떻게 되는지 제대로 명시해놓지 않았다.

프로그래머스의 지문은 별로 좋지 않은 문제들이 꽤 있는 것 같다.

본 문제의 지문이 이해가 가지 않는다면 아래 지문을 다시 보면 좀 이해가 될 것이다.

출처: https://school.programmers.co.kr/questions/53163

 

우선 변수를 다음과 같이 선언했다.

 

    int answer = 0;     // 모든 트럭이 다리를 건너는 최소 시간

    Queue<Integer> ready = new LinkedList<>();  // 대기 트럭 무게 큐

    List<Truck> crossing = new ArrayList<>();   // 다리를 건너는 트럭 리스트

 

 

다리를 건너는 트럭 리스트(crossing)의 타입인 Truck 클래스는 아래와 같이 정의했다.

 

    class Truck {

        int weight;     // 트럭의 무게

        int time;       // 트럭이 다리를 건너는 경과 시간

       

        Truck(int weight, int time) {

            this.weight = weight;

            this.time = time;

        }

    }

 

 

대기 트럭 무게 큐(ready)에 문제에 주어진 truck_weights 배열의 값들을 모두 추가한다.

 

    // 모든 트럭 무게를 대기 트럭 무게 큐에 추가

    for (int truck_weight : truck_weights) {

        ready.add(truck_weight);

    }

 

 

아래에 있는 while 문의 루프를 한번 돌 때마다 경과 시간(answer)이 1씩 증가한다.

 

다리를 건너는 중인 트럭 리스트(crossing)에 담긴 트럭들을 모두 탐색하고, 트럭의 경과 시간이 bridge_length와 같은 트럭들을 제거한다.

트럭을 제거할 때에는 트럭 무게(truck.weight)를 다리를 건너는 트럭들의 총 무게(crossingWeight)에서 빼고, 다리를 지난 트럭의 개수를 1 증가한다.

그리고 다리를 지난 트럭의 인덱스(crossedIdx)를 저장해서 다리를 건너는 중인 트럭 리스트(crossing)을 모두 탐색한 이후 crossing에서 crossedIdx에 해당하는 트럭을 제거한다.

리스트에서 트럭 제거를 for문 안에서 하지 않는 이유는 for문 자체가 crossing 리스트의 인덱스를 기준으로 탐색하는 건데, 예를들어 crossing 리스트에서 인덱스가 1에 해당하는 트럭을 제거하면 바로 뒤에 있던 트럭이 이제 crossing 리스트 내의 1번째 인덱스에 해당하는 값으로 변하는데, for문의 증가식(i++)에 의하여 인덱스 2로 넘어가면 제거한 트럭의 바로 뒤에 있던 트럭은 무시하기 때문이다.

 

i = 0일 때 0번째 트럭인 트럭0을 제거하고

제거 전 List<Truck> crossing (다리를 건너는 중인 트럭 리스트)
i	0	1	2
Truck	트럭0	트럭1	트럭2

 

제거 이후의 0번째 트럭은 트럭1이 되어버린다.

이 때 i = 1로 넘어가버리면 자동으로 트럭1은 무시되고, 바로 트럭2로 넘어간다.

그러므로 for문 내에서 crossing 리스트의 인덱스를 제거하지 않고, for문 밖에서 제거하는 것이다.

제거 후 List<Truck> crossing (다리를 건너는 중인 트럭 리스트)
i	0	1
Truck	트럭1	트럭2

 

문제에 주어진 조건을 만족하면 대기 트럭 무게 큐(ready)에서 트럭 무게를 뽑은 값(ready.poll())을 이용하여 트럭을 생성해서 crossing 리스트에 추가하고 대기 트럭 무게 큐에서 뽑은 트럭 무게를 트럭들의 총 무게(crossingWeight)에 더한다.

 

사실 이 로직은 텍스트로 보기보다는 코드와 함께 주석을 보는 것이 더 좋을 것 같다.

 

    int crossingWeight = 0;     // 다리를 건너는 트럭들의 총 무게

    int crossedCount = 0;       // 다리를 지난 트럭의 개수

   

    // 다리를 지난 트럭의 개수가 문제에 주어진 트럭 개수와 같아질 때까지 반복

    while (crossedCount < truck_weights.length) {

        answer++;   // 모든 트럭이 다리를 건너는 최소 시간 1 증가

        int crossedIdx = -1;    // 다리를 지난 트럭의 인덱스

       

        // 다리를 건너는 중인 트럭들을 모두 탐색

        for (int i = 0; i < crossing.size(); i++) {

            Truck truck = crossing.get(i);  // i번째 트럭

            truck.time++;   // i번째 트럭의 경과 시간 1 증가

           

            // i번째 트럭의 경과 시간이 다리에 올라갈 수 있는 트럭 수와 같다면

            // 다리를 모두 건넌 것

            if (truck.time == bridge_length) {

                // 다리를 건너는 중인 트럭들의 총 무게에서 i번째 트럭의 무게 빼기

                crossingWeight -= truck.weight;

                crossedCount++; // 다리를 지난 트럭의 개수 1 증가

                crossedIdx = i; // 다리를 지난 트럭의 인덱스에 현재 트럭 인덱스 i 저장

            }

        }

       

        // 다리를 지난 트럭의 인덱스가 -1이 아니라면 다리를 지난 트럭이 존재하는 것

        if (crossedIdx != -1) {

            // 다리를 건너는 중인 트럭 리스트에서 해당 인덱스 제거

            crossing.remove(crossedIdx);    

        }

       

        // 대기 트럭 큐가 비어있지 않고,

        // 다리를 건너는 중인 트럭의 수가 다리에 올라갈 수 있는 트럭 수보다 작고,

        // 다리를 건너는 트럭들의 총 무게와 대기 트럭 무게 큐의 가장 앞에 있는 트럭 무게의 합이

        // 다리가 견딜 수 있는 무게 이하라면

        if (!ready.isEmpty()

            && crossing.size() < bridge_length

            && crossingWeight + ready.peek() <= weight) {

            int nowWeight = ready.poll();   // 대기 트럭 무게 큐에서 뽑기

            // 위에서 뽑은 트럭 무게와 0초 경과 시간을 갖는 트럭을 다리를 건너는 트럭 리스트에 추가

            crossing.add(new Truck(nowWeight, 0));  

            // 다리를 건너는 트럭들의 총 무게에 위에서 뽑은 트럭 무게 더하기

            crossingWeight += nowWeight;    

        }

    }

   

    return answer;  // 모든 트럭이 다리를 건너는 최소 시간 리턴

 

 

 

전체 코드

import java.util.*;
 
class Solution {
    public int solution(int bridge_length, int weight, int[] truck_weights) {
        int answer = 0;     // 모든 트럭이 다리를 건너는 최소 시간
        Queue<Integer> ready = new LinkedList<>();  // 대기 트럭 무게 큐
        List<Truck> crossing = new ArrayList<>();   // 다리를 건너는 트럭 리스트
         
        // 모든 트럭 무게를 대기 트럭 무게 큐에 추가
        for (int truck_weight : truck_weights) {
            ready.add(truck_weight);
        }
        
        int crossingWeight = 0;     // 다리를 건너는 트럭들의 총 무게
        int crossedCount = 0;       // 다리를 지난 트럭의 개수
        
        // 다리를 지난 트럭의 개수가 문제에 주어진 트럭 개수와 같아질 때까지 반복
        while (crossedCount < truck_weights.length) {
            answer++;   // 모든 트럭이 다리를 건너는 최소 시간 1 증가
            int crossedIdx = -1;    // 다리를 지난 트럭의 인덱스
            
            // 다리를 건너는 중인 트럭들을 모두 탐색
            for (int i = 0; i < crossing.size(); i++) {
                Truck truck = crossing.get(i);  // i번째 트럭
                truck.time++;   // i번째 트럭의 경과 시간 1 증가
                
                // i번째 트럭의 경과 시간이 다리에 올라갈 수 있는 트럭 수와 같다면
                // 다리를 모두 건넌 것
                if (truck.time == bridge_length) {
                    // 다리를 건너는 중인 트럭들의 총 무게에서 i번째 트럭의 무게 빼기
                    crossingWeight -= truck.weight;
                    crossedCount++; // 다리를 지난 트럭의 개수 1 증가
                    crossedIdx = i; // 다리를 지난 트럭의 인덱스에 현재 트럭 인덱스 i 저장
                }
            }
            
            // 다리를 지난 트럭의 인덱스가 -1이 아니라면 다리를 지난 트럭이 존재하는 것
            if (crossedIdx != -1) {
                // 다리를 건너는 중인 트럭 리스트에서 해당 인덱스 제거
                crossing.remove(crossedIdx);    
            }
            
            // 대기 트럭 큐가 비어있지 않고,
            // 다리를 건너는 중인 트럭의 수가 다리에 올라갈 수 있는 트럭 수보다 작고,
            // 다리를 건너는 트럭들의 총 무게와 대기 트럭 무게 큐의 가장 앞에 있는 트럭 무게의 합이
            // 다리가 견딜 수 있는 무게 이하라면
            if (!ready.isEmpty()
                && crossing.size() < bridge_length 
                && crossingWeight + ready.peek() <= weight) {
                int nowWeight = ready.poll();   // 대기 트럭 무게 큐에서 뽑기
                // 위에서 뽑은 트럭 무게와 0초 경과 시간을 갖는 트럭을 다리를 건너는 트럭 리스트에 추가
                crossing.add(new Truck(nowWeight, 0));  
                // 다리를 건너는 트럭들의 총 무게에 위에서 뽑은 트럭 무게 더하기
                crossingWeight += nowWeight;    
            }
        }
        
        return answer;  // 모든 트럭이 다리를 건너는 최소 시간 리턴
    }
}
 
class Truck {
    int weight;     // 트럭의 무게
    int time;       // 트럭이 다리를 건너는 경과 시간
    
    Truck(int weight, int time) {
        this.weight = weight;
        this.time = time;
    }
}