프로그래머스 코딩테스트 연습문제: 다리를 지나는 트럭

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

코딩테스트 연습 - 다리를 지나는 트럭 | 프로그래머스

문제 설명

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

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

경과 시간 다리를 지난 트럭 다리를 건너는 트럭 대기 트럭

경과시간                                        다리를 지난 트럭                         다리를 건너는 트럭                        대기 트럭

0	[]	[]	[7,4,5,6]
1~2	[]	[7]	[4,5,6]
3	[7]	[4]	[5,6]
4	[7]	[4,5]	[6]
5	[7,4]	[5]	[6]
6~7	[7,4,5]	[6]	[]
8	[7,4,5,6]	[]	[]

 

따라서, 모든 트럭이 다리를 지나려면 최소 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 이하입니다.

입출력 예

bridge_lengthweighttruck_weightsreturn

2	10	[7,4,5,6]	8
100	100	[10]	101
100	100	[10,10,10,10,10,10,10,10,10,10]	110

 

문제가 처음 주어졌을 때 중점적으로 생각한 부분은 크게 (1) 트럭의 대기순서 + 다리의 교량이 견딜 수 있는 무게, (2) 트럭이 다리를 건너는데 걸리는 시간(결국 다리의 길이와 같다는 것을 알 수 있다)으로 두 가지였다. 두 가지 요소를 고려하여서 코드를 작성하였다.

import java.util.ArrayList;
import java.util.List;

public class Solution {
    static int cnt;

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

        List<Integer> truckList = new ArrayList<>();
        List<Integer> ing = new ArrayList<>();
        List<Integer> eachCount = new ArrayList<>();

        for (int i : truck_weights)
            truckList.add(i);

        int cnt = 0; // 경과시간 카운트! (초기화)

        while (!truckList.isEmpty() || !ing.isEmpty()) {
            cnt++;
            int weightsum = ing.stream()
                    .mapToInt(Integer::intValue)
                    .sum();

            if (truckList.size() != 0) {
                if (truckList.get(0) + weightsum <= weight) {
                    eachCount.add(0);
                    ing.add(truckList.get(0));
                    weightsum += truckList.get(0);
                    truckList.remove(0);
                }
            }
            //현재 지나가고있는 트럭들 시간 카운트하기 카운트시간 == 다리길이 면 통과한것으로 처리 리스트(2개) 제외
            for (int i = 0; i < eachCount.size(); i++) {
                eachCount.set(i, eachCount.get(i) + 1);
                if (eachCount.get(i) == bridge_length) {
                    eachCount.remove(i);
                    ing.remove(i);
                    i--;
                }
            }
        }

        answer = cnt + 1;
        return answer;
    }


    public static void main(String[] args) {

        int bridge_length1 = 2;
        int bridge_length2 = 100;
        int bridge_length3 = 100;

        int weight1 = 10;
        int weight2 = 100;
        int weight3 = 100;

        int[] truck_weights1 = {7, 4, 5, 6};
        int[] truck_weights2 = {10};
        int[] truck_weights3 = {10, 10, 10, 10, 10, 10, 10, 10, 10, 10};

        Solution sol = new Solution();
        System.out.println("1번답:" + sol.solution(bridge_length1, weight1, truck_weights1));
        System.out.println("2번답:" + sol.solution(bridge_length2, weight2, truck_weights2));
        System.out.println("3번답:" + sol.solution(bridge_length3, weight3, truck_weights3));

    }

처음에 코드를 짤 때 원하는 값보다 결괏값이 작게 나왔다. 코드를 분석하다 보니, 대기하는 차량은 없지만 다리를 건너고 있는 차량이 있는 경우의 수를 생각하지 못해서, while 반복문의 조건식을 잘못 설정하여서 예상 반복 횟수보다 짧게 반복을 진행하였다. 이후! ing.Empty()  
조건을 추가하면서 원하는 결괏값이 정상적으로 출력되었다. 제출해보니 정답으로 처리되었다. 

해당 문제는 Queue의 개념을 이용하면 좋을 것이라 생각했지만, Queue 알고리즘이 익숙지 않아서, 위와 같이 코드를 짰다. 
아래는 다른 사람의 풀이를 참고한 내용이다. Queue와 Truck 객체를 이용하여 문제 풀이를 진행하였다. (한눈에 보기에도 깔끔하게 코드가 깔끔해 보인다)

public class Solution {


    class Truck { //내부 클래스 선언 (문제 풀이때는 클래스 따로 선언 불가능하니 내부 클래스 선언하면 괜찮을...듯?)

        int weight;
        int move;

        public Truck(int weight) {
            this.weight = weight;
            this.move = 1;
        }

        public void moving() {
            move++;
        }

    }

    public int solution(int bridgeLength, int weight, int[] truckWeights) {
        
        Queue<Truck> waitQ = new LinkedList<>();
        Queue<Truck> moveQ = new LinkedList<>();

        for (int t : truckWeights) {
            waitQ.offer(new Truck(t));
        }

        int answer = 0;
        int curWeight = 0;

        while (!waitQ.isEmpty() || !moveQ.isEmpty()) {
            answer++;

            if (moveQ.isEmpty()) {
                Truck t = waitQ.poll();
                curWeight += t.weight;
                moveQ.offer(t);
                continue;
            }

            for (Truck t : moveQ) {
                t.moving();
            }

            if (moveQ.peek().move > bridgeLength) {
                Truck t = moveQ.poll();
                curWeight -= t.weight;
            }

            if (!waitQ.isEmpty() && curWeight + waitQ.peek().weight <= weight) {
                Truck t = waitQ.poll();
                curWeight += t.weight;
                moveQ.offer(t);
            }
        }

        return answer;

    }

Queue는 LinkedList()로 구현되고, LinkedList의 메소드는 아래와 같다. (필자와 같이 LinkedList가 익숙하지 않은 분들을 위해 퍼왔다) 

         * Queue(큐)는 FIFO (First In, First Out) 즉 선입 선출하는 자료구조이다.
         * LinkedList로 나타내며 주요 메소드는 아래와 같다.
         * public void offer(Element data) // 순차 보관
         * public Element poll(); // 가장 먼저 보관한 값 꺼내고 반환
         * public Element peek(); // 가장 먼저 보관한 값 단순 참조 (꺼내지 않는다)
         * public boolean empty(); // 비어있는지 판별