[programmers] 다리를 지나는 트럭 (Java)

[다리를 지나는 트럭] 

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

프로그래머스

 

[접근 방법]

트럭을 별도의 클래스로 만든다.

int weight : 트럭의 무게

int move : 트럭의 이동거리

 

큐를 이용해서 문제를 해결하였다.

'대기 중인 트럭'을 저장하는 'waitQ' 와 '다리 위에 있는 트럭'을 저장하는 'moveQ' 를 선언하였다.

 

시간을 뜻하는 answer에 +1 을 추가하면서 진행한다.

moveQ가 비어있을 경우, waitQ의 첫 트럭을 moveQ에 추가하고, 현재 다리위 트럭 무게 합을 누적한다.

 

다리 위에 있는 트럭들의 이동거리를 추가한다.

 

다리 위에 있는 가장 앞선 트럭의 이동거리가 다리 길이를 넘어서는 경우, 다리에서 내린 것으로 간주하고 moveQ 에서 지운다. 그리고 다리위 트럭 무게 합에서 뺀다.

 

다리위 트럭 무게 합을 통해 다음 트럭이 다리에 올라갈 수 있는지 확인하고 가능하면 다리에 올린다.

 

waitQ 와 moveQ 가 빌때 까지 반복문을 사용하여 반복한다.

 

[Java 코드]

//코딩테스트 연습 스택/큐 다리를 지나는 트럭
//https://school.programmers.co.kr/learn/courses/30/lessons/42583

import java.util.*;

public class PM_42583 {

  
  public class Truck {
    int weight;
    int move;

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

    public void moving() {
      move++;
    }
    
  }

  public int solution(int bridge_length, int weight, int[] truck_weights) {
    //대기중인 트럭 저장
    Queue<Truck> waitQ = new LinkedList<>();
    //다리위에 있는 트럭 저장
    Queue<Truck> moveQ = new LinkedList<>();

    //대기중인 트럭 저장 (waitQ 초기화)
    for (int t : truck_weights) {
      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 > bridge_length) {
        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;
  }
}

 

[Rewind]

1. 어려웠던 점

- 큐를 사용해야 하는 것은 알고 있었지만, 문제 해결방식을 어떻게 구성해야 하는가에 대한 아이디어가 떠오르지 않아 어려웠다.

- 결과적으로 문제를 독자적인 힘으로 해결하지 못하고 답을 확인한 것에 스스로 화가 났다.

 

2. 알게된 점

- 큐를 이용해 해결방식을 구축하는 한가지 예시를 알게되었다.

- 별도의 클래스(트럭)을 구성하여, 해결하는 것을 적극적으로 사용해야 한다고 생각하였다.

 

3. 개선방안

- 여러 문제를 많이 풀어봐야 한다고 생각한다.

- 자료구조에 기초가 부족하다고 생각한다.

- 별도 클래스를 통해 문제에서 나오는 오브젝트를 객체로 구성해서 해결하는 것을 적극적으로 사용해야 한다.