백준 13335 트럭 <실버 1> - 자바 Queue

칙칙폭폭

 

처음에 봤을때 이거 그냥 배열로도 되겠는데,, 하다가

문제가 큐로 풀어주세요~ 하는거 같아서 메소드 찾아가면서 풀어봤다.

 

먼저 n w L 이 주어진다. 

n -> 트럭 수, w -> 다리 길이, L -> 최대 하중

모든 트럭이 다리를 지나가는 시간을 계산하는 문제고, 다리 하중보다 높으면 트럭을 올라갈 수 없다.

또한 1초에 1칸씩 이동하는 개념을 갖고있다.

 

간단하게 생각했을때 트럭이 없어질때까지 반복해서, 다리에 올릴 수 있으면 올리고, 하중때문에 못올린다면 0값을 넣어서 밀어 넣는 식으로 생각했다. 내릴때는 0번째 위치면 내리고, 아닌 친구들은 idx를 1씩 빼면서 로케이션을 바꿔주면 되겠다 했다.

 

근데 Queue를 써버리면 그냥 문제 흐름 그대로 FIFO(선입선출)기 때문에 인덱스 관리를 할 필요가 없어져 간단해졌다.

또한 풀다보니까 트럭을 다 올리고 나서도 내리는 과정이 필요하기에 다리가 비어있는걸 기준으로 반복문을 작성했다.

 

 >> Queue

 

먼저 넣은 자료가 먼저 출력되는 구조로, front와 rear로 나뉘어 front는 출력 및 삭제, 뒤는 rear로 삽입 연산만 수행한다.

BFS(그래프 넓이 우선 탐색)을 사용하고 입력이 많아지면 처리하지 못하는 프로세스들을 버퍼에 넣어 대기시킨다.

 

 >> 메서드

큐 선언 방식
Queue<Integer> queue = new LinkedList<>();
요소 추가
queue.add(element); -> 예외 발생	queue.offer(element); -> 값 리턴
요소 삭제
queue.remove(); -> 예외 발생	queue.poll(); -> 값 리턴
요소 검사
return queue.element(); -> 예외 발생	return queue.peek(); -> 값 리턴
큐 크기 확인	대기열이 비었나 확인
queue.size();	queue.isEmpty();

 

 

import java.util.*;
 
public class Main {
    public static void main(String[] args){
        //input
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int w = sc.nextInt();
        int L = sc.nextInt();      
        
        Queue<Integer> truck = new LinkedList<>();
        Queue<Integer> bridge = new LinkedList<>();
        
        for(int i = 0; i<n; i++) {
            truck.offer(sc.nextInt());
        }     
        
        sc.close();
        
        int answer = 0;
        int weight = 0;
        
        for(int i = 0; i<w; i++) {
            bridge.offer(0); // 0으로 먼저 채워준다.
        }
        
 
               
        //logic
        while ( !bridge.isEmpty()){
            answer ++;
            weight -= bridge.poll(); // 다리에서 트럭 빼기
            if( !truck.isEmpty()) {  // 트럭이 남아있고
                if(truck.peek() + weight <= L) { // 최대하중보다 낮다면
                    weight += truck.peek();      // 무게 추가
                    bridge.offer(truck.poll());  // 트럭 다리로 이동    
                }else {
                    bridge.offer(0);             // 하중보다 높다면 0으로 자리 채우기
                }
            }
        }// while
        
        //output
            System.out.print(answer);
     
    }
   
}

 

Queue로 간단하게 풀리는 문제였다.

자료구조를 배울때 구현해보고 실습했어야 했는데, 자바 구현능력이 부족해서 못했었던게 후회가 남는다..

감자는 오늘도 싹이 하나 핍니다..