프로그래머스 lv2 다리를 지나는 트럭

문제 링크

다리를 지나는 트럭

풀이

• 큐를 사용해야하는 문제임은 깨달았다.
• 그런데 규칙 찾다가 머리가 깨지는 줄.
• 내가 잘못 생각하고 있었다. 트럭을 큐에 올리고, 그걸 이용해서 시간을 재면 되었는데 그렇게 생각을 못하고 있었음.
• 다른 분이 푼 풀이를 보고나서야 깨달았는데, 트럭을 큐에 올린 다음 while문을 통해서 그 다음 트럭이 들어오는 경우, 그 다음 트럭이 무게 제한때문에 못들어오는 경우를 체크해주면, 해당 트럭이 나갈때까지 시간을 체크할 수 있었다.
• 다리에 트럭을 넣는 조건은 3가지가 있다.

1. 큐가 비어있는 경우
   • 이런 경우에는, 그냥 다리(큐)에 트럭을 올려주면 된다. 그 다음에는 현재 다리위의 트럭 무게 합에 올라간 트럭의 무게를 더해주고, 다리위에 올라갔으니 시간도 + 1 해준다.
2. 큐가 다리길이만큼 가득차지 않은 경우
   • 큐가 다리길이만큼 가득차지 않은 경우에는 다음 트럭의 무게와 현재 다리위에 올라가있는 트럭의 무게를 더해서 최대 무게를 넘는지 확인해야한다.
   • 만약 최대무게를 넘는다면 큐에 임의의 값 0을 더해서 위에 올라간 트럭이 한 칸 앞으로 전진할 수 있게 하고,
   • 아니라면 큐에 트럭을 올리고, 무게 합에 올라간 트럭 무게를 더한다.
   • 위의 두 과정 모두 큐(다리)에 뭔가를 넣기에 시간은 동일하게 + 1이다.
3. 큐가 가득 찬 경우
   • 이때는 큐의 가장 앞에 들어간 트럭이 나갈때가 되었다는 것이기에, poll을 사용해서 빼고 빼준만큼 무게에서도 같이 빼준다.

이 세가지를 고려하고 코드를 짜면 다음과 같다.

import java.util.LinkedList;
import java.util.Queue;

class Solution {
    public int solution(int bridge_length, int weight, int[] truck_weights) {
        int answer = 0;
        int weightSum = 0;
        Queue<Integer> queue = new LinkedList<>();

        for(int truck : truck_weights){
            while (true){
                if(queue.isEmpty()){ // 다리가 빈 경우
                    queue.add(truck);
                    weightSum += truck;
                    answer++;
                    break;
                } else if(queue.size() == bridge_length){ // 다리가 꽉 찬 경우, 비워준다.
                    weightSum -= queue.poll();
                } else {
                    if(weightSum + truck <= weight){ // 새로웉 트럭을 올려도 weight를 넘기지 않으면?
                        queue.add(truck);
                        weightSum += truck;
                        answer++;
                        break;
                    } else {
                        // 이미 트럭이 올라가있는데, 큐가 안찼으면.. 0으로 넣어서 보내준다.
                        queue.add(0);
                        answer++;
                    }
                }
            }
        }
        
        // 마지막 트럭은 다리길이만큼 보내준다.
        answer+= bridge_length;

        return answer;
    }
}

소감

• 주말에 코테 한번 보고 그 뒤로 처음 풀어보는 코테
• 여전히 나는 발전하지 않았다.