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

 

프로그래머스 level 2 - 다리를 지나는 트럭 풀이

---

 

 

 

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

 

 

 

 

문제 간단 요약

 

 

무게를 가진 트럭들이 존재하는데 특정 길이와 특정 무게를 가진 다리를 모두 건너야된다.

 

모든 트럭들이 무사히 다리를 모두 건넌 시점에서의 시간(초)을 구하는게 문제이다.

 

 

 

 

 

나의 풀이

 

 

다리길이와 초당 트럭이 앞으로 나아가야한다는 것 때문에 처음에 풀이를 생각하는데 애를 많이 먹은 것 같다.

 

 

 

결국 트럭은 들어온 놈 부터 나간다.

 

-> 큐를 이용해야겠다는 생각을 했다.

 

 

 

결국 다리길이는 정해져있다. 다리에 몇 개의 트럭이 있던 상관없이 하나의 트럭 관점에서는

 

다리로 입장한 시점과 다리에서 나가는 시점은 항상 같다

 

-> 큐에 다리에 트럭이 입장할 때의 시점을 저장한다.

 

 

 

매 초마다 현재 다리의 무게와 앞으로 지나가야할 트럭의 무게를 검사한다.

 

현재 다리에 존재하는 트럭의 수는 큐에 보관된 해당 트럭들의 입장 시점 수일 것이다.

 

 

 

 

다음과 같은 입력을 예시로 들어보자

 

Bridge_length	Weight	Truck
5	10	[7,4,5,6]

 

 

 

 

 

1초라는 시점에서 다리의 상황은 다음과 같을 것이다.

 

다리에 트럭이 올라왔다는 것을 큐에 해당 트럭을 넣었다는 것으로도 생각해보자

 

다리의 무게제한이 10이니 다음 트럭은 현재 무게 7짜리 트럭이 다리에 존재하는 이상 올라오지 못할 것이다.

 

 

 

 

시점이 6초일 때 첫번째 트럭이 다리를 벗어나게 될 수 있을 것이다.

 

그리고 이 시점에 다리에는 아무트럭이 없으니 무게4짜리 두번째 트럭이 올라올 수 있다.

 

 

 

 

 

다음시점으로 넘어가보자

 

 

 

 

 

10 > 4 + 5로 다리에 두개의 트럭이 존재할 수 있어 5무게짜리 트럭이 바로 올라오게 되었다.

 

현재 맨 앞에 있는 무게4짜리 트럭이 다리를 나가는 시점을 확인해보자

 

 

 

 

뒤의 상황이 어떻든 상관없이 맨 앞의 트럭은 자기가 들어온 시점을 바탕으로 항상 정해진 시점에 다리를 벗어나게 된다.

 

여기서 다음과 같은 공식을 생각해볼 수 있다.

 

 (현재 시점 - 트럭이 들어온 시점) == 다리 길이

 

위의 공식이 성립하는 시점이 맨 앞의 트럭이 나가는 시점이기때문에 큐에서 해당 트럭을 제거해준다.

 

그렇게 되면 현재 다리에 남아있는 것들 중 맨 앞에 있는 트럭을 큐는 최우선으로 바라볼 것이다.

 

 

 

 

 

이제 현재 과정과 무관하게 아래의 그림을 한번 보자

 

 

 

현재 다리에 3, 3, 3 무게의 트럭이 존재해 무게가 4인 트럭은 다리에 올라올 수 없었다.

 

하지만 다음 시점으로 넘어가면서 맨 앞에 있는 트럭이 다리를 벗어나게 된다면 4번트럭은 들어올 수 있게 된다.

 

여기서 다리의 무게와 현재 다리에 가해지는 부하의 현황(현재 다리에 존재하는 트럭 무게의 합)을 매 초 검사해야한다는 것을 알 수 있다.

 

 

 

 

자바 풀이 코드

 

 

import java.util.LinkedList;
import java.util.Queue;
class Solution {
  public static int solution(int bridge_length, int weight, int[] truck_weights) {
    int answer = 0;
    Queue<Integer> currentQueue = new LinkedList<>();

    // 트럭무게 배열 index
    int index = 0;
    // 흘러갈 시간
    int sec = 0;
    // 다리를 건넌 트럭의 수이자 현재 넣어야 할 트럭의 인덱스이기도 하다.
    int count = 0;
    // 다리위에 있는 트럭들 무게의 합.
    int tempWeight = 0;

    while (true) {
      // 모든 트럭이 다리를 지나가면 반복문 종료
      if (count == truck_weights.length) {
        break;
      }
      sec++;
      // 경과시간 - 가장 처음 추가된 트럭이 추가된 시점이 다리 길이면
      // 해당 트럭은 다리를 건넌 것이다.
      // 큐에서 해당 트럭이 다리로 올라온 시점을 빼줘야함.
      // 그래야 다음 트럭에 대해 계산 가능
      if (!currentQueue.isEmpty() && sec - currentQueue.peek() == bridge_length) {
        // 현재 다리위에 있는 트럭들의 무게에서 빼줘야함.
        tempWeight -= truck_weights[count];
        // 다리를 건넌 트럭 수를 추가해준다.
        count++;
        //큐에서 지금 빼는 트럭이 다리에 올라온 시점을 빼줌
        currentQueue.poll();
      }

      // 현재 다리에 있는 트럭들의 무게에 새로운 트럭을 추가해도
      // 혀옹 무게를 넘지 않으면 추가해준다.
      // 이미 마지막 트럭도 넣었으면 그만 한다.
      if (index!= truck_weights.length && weight >= truck_weights[index] + tempWeight) {
        tempWeight += truck_weights[index++];
        // 트럭이 추가 될 때의 경과시간을 큐에 넣어줌
        currentQueue.add(sec);
      }
      // 시간은 계속 흘러감
      

    }
    return sec;
  }
}