[Java] level2 - stackNqueue_42583

문제 링크

풀이

Input

  • (int) bridge_length = 다리 길이
  • (int) weight = 다리가 견딜 수 있는 트럭 무게의 합
  • (int[]) trucks_wieght = 트럭의 무게들이 기록되어있는 Array

주요 변수

  • total_time : 모든 트럭이 다리를 건너는데 걸린 시간을 담고있음
  • weight_sum : 다리에 올라간 트럭 무게의 총합을 담고있음
  • truck_idx : truck_weights Array에서의 idx를 의미하며, 트럭이 다리에 올라갔는지 & 다리가 견딜 수 있는 무게(=weight) 값이랑 비교하기 위해 쓰인다.

로직

  • 다리(bridge)를 표현할 0으로 채워진 Queue를 만들어준다
    • Queue의 크기(size) = 다리의 길이(bridge_length) => bridge_queue
Queue<Integer> bridge_que = new LinkedList<>();
        for (int i = 0; i < bridge_length; i++) {
            bridge_que.offer(0); // 최초에 트럭이 안올라와있으니 0으로 채운다
        }
  • while문을 통해서 트럭이 다리를 건너는 상황을 시뮬레이션 할 수 있도록해준다
    • while문 한번돌때마다 1초임 = 트럭이 한칸씩 움직임
    • while문 조건 : bridge_que가 비었는지 확인
      • 비었다면 트럭이 모드 건넜다는 뜻 = while문 멈춘다
    • while문 내에서 로직
      • 다리를 건너게 함 : bridge_que 맨앞에 있는 값을 뽑아냄(bridge.offer())
      • 현재 다리위에 있는 트럭들의 무게 = 현재 다리위에 있는 트럭들의 무게 - 이번에 건너는 무게(트럭무게 or 0)
      • 현재 다리위에 있는 트럭들의 무게 + 이번에 올리고자하는 트럭의 무게 <= 다리가 견딜 수 있는 트럭 무게의 합
        • 트럭을 올릴 수 있다면 => bridge_que트럭의 무게값을 넣어준다
        • 트럭을 올릴 수 없다면 => bridge_que0을 넣어준다
while (!bridge_que.isEmpty()) { //bridge_que가 비었다는건 모든 트럭이 다 건넜다는 것을 뜻함
            int popped = bridge_que.poll(); // 1초 지나서 한칸씩 전진해야하니깐 제일 앞에 있는거 하나 뺴줘야함, poll() 해준건 다리 다 지나간거
            weight_sum -= popped; // 다리 다 지나간 것 만큼 무게 뺴줘야함
            if (truck_idx < truck_weights.length) { // truck_idx는 truck_weights의 index를 벗어날 수 없다
                if (weight_sum + truck_weights[truck_idx] <= weight) { // 최대 무게 이하여야함
                    bridge_que.offer(truck_weights[truck_idx]); // 트럭이 다리에 진출 line 18에서 하나 뺴줬으니깐 하나 넣어줘야함
                    weight_sum += truck_weights[truck_idx]; // 다리에 올라와있는 트럭 무게 추가
                    truck_idx++; // 다음에 올릴 truck의 idx
                } else { // else는 무게때문에 트럭을 더 추가할 수 없을때는 0을 채워줌 진입
                    bridge_que.offer(0);
                }
            }
            total_time++; // 1초 지날때마다 1씩 올라감
        }

전체 코드

좋은 웹페이지 즐겨찾기