[프로그래머스/Lv. 2] 다리를 지나는 트럭 (JAVA)

🔺 문제

프로그래머스

 

 

🔺 코드

import java.util.*;
 
class Solution {
    public int solution(int bridge_length, int weight, int[] truck_weights) {
 
        int time = 0;   // 소요 시간
        int sum = 0;    // 다리 건너는 트럭 무게들 합
        
        Queue<Integer> q = new LinkedList<>();
        
        for(int t : truck_weights) {
            while(true) {
                // 1] 큐가 비어있는 경우 = 다리 위에 아무 트럭도 없는 경우
                if(q.isEmpty()) {
                    q.offer(t);
                    sum += t;
                    time++;    // 다리에 오를 때만 시간 추가
                    break;
                }
                // 2] 큐에 다리 길이만큼 트럭이 다 찬 경우
                else if(q.size() == bridge_length) {
                    sum -= q.poll();
                }
                // 3] 다리 길이만큼 큐가 차지 않은 경우
                else {
                    if(sum + t <= weight) {    // weight 값 넘지 않는 선에서 새 트럭을 다리에 올림
                        q.offer(t);
                        sum += t;
                        time++;
                        break;
                    }
                    else {
                        q.offer(0);    // 넘는 경우, 0을 넣어 트럭이 다리를 건너게 함
                        time++;                        
                    }
                }
            }
        }
        
        return time + bridge_length;    // 여지껏 걸린 시간 + 마지막 트럭 통과 시간(= 다리 길이)
    }
}

 

 

🧩  해결 아이디어

• 큐 (= 다리)

1. 큐가 빈 경우 = 다리 위에 아무 트럭도 없는 경우

  1-1. 다음 트럭 삽입 (= 큐에 추가)

  1-2. 현재 무게 갱신 (sum += 올라간 트럭 무게)

  1-3. 시간 + 1

 

2. 큐가 가득차지 않은 경우

  2-1. 다리 위 트럭들의 무게합 <= 최대 무게 (weight)인 경우

        - 트럭을 다리에 올림 (큐에 추가)

        - 현재 무게 갱신 (sum += 올라간 트럭 무게)

        - 시간 + 1

 

 2-2. 다리 위 트럭들의 무게합 > 최대 무게(weight)인 경우

       - 다리에 올릴 수 없음

       - 값을 0을 넣어 이미 있는 트럭이 다리를 지나가도록 함

       - 시간 + 1

 

 

 

---

🔺 다른 풀이들

- 조금 다르다.

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

 

- 클래스 활용하시고, 큐를 2개 활용하셨다!

내가 첨에 이렇게 생각하긴 했는데 끝까지 구현을 못 해서 틀리긴 했다만..

import java.util.*;

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;
    }
}

---

💬 느낀 점

아앗 조건 나누다가 시간 지남...

담엔 잘 풀장...

 

 

1회독	2회독	3회독	4회독	5회독
V

---

(참고)

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

 

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