칸비

개발 찍어먹기

[자료구조]-Queue와 ArrayList

어제 푼 다리를 지나는 트럭 문제를 ArrayList로 풀었다. 여러가지 코드를 보니 대부분 Queue를 이용했다. 그래서 Arraylist를 Queue로 코드를 변경했다. 변경하니 좀더 만들기는 편했다. 이미 풀어본 문제라서 그런가…?

문제

주석에 모든 설명이 나와있다.

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

class Solution {
    public int solution(int bridge_length, int weight, int[] truck_weights) {
        int answer = 0;
        int weight_sum = 0;//현재 다리 무게
        
        Queue<Integer> before_Q = new LinkedList<Integer>();//다리 건너기 전 큐
        Queue<Integer> Q = new LinkedList<Integer>();//다리 큐
        Queue<Integer> after_Q = new LinkedList<Integer>();//다리 건넌 후 큐
        
        for(int i=0;i<truck_weights.length;i++) before_Q.offer(truck_weights[i]);//건너기 전 큐 초기화
        for(int i=0;i<bridge_length;i++) Q.offer(0);//다리 0으로 초기화
        
        while(!before_Q.isEmpty() || !Q.isEmpty()){
            answer++;
            
            if(Q.peek()!=0){//다리 끝에 0이 아니면
                weight_sum-=Q.peek();//다리에 무게 빼기
                after_Q.offer(Q.poll());//옮기기
            }
            else Q.remove();//다리 끝에 0이면 삭제
            
            if(before_Q.peek()!=null){//다리 전큐가 비어있지 않으면
                if(weight_sum+before_Q.peek()<=weight){//무게가 넘지 않으면
                    weight_sum+=before_Q.peek();
                    Q.offer(before_Q.poll());
                }
                else Q.offer(0);//무게가 넘으면 0을 다리에 채운다
            }
        }
        return answer;
    }
}

ArrayList와 Queue의 메소드

1. ArrayList 메소드의 종류
ArrayList<Integer> bridge = new ArrayList<Integer>(); //선언
bridge.add(0) // 0 추가
bridge.add(0 , 2) // index 0에 2추가
bridge.size() // 크기를 integer형태로 return
bridge.remove(0) // index 0인 원소 삭제
bridge.clear();  // 모든 값 제거
bridge.get(0); // index 0인 원소 return
bridge.contains(1)); // list에 1이 있는지 검색 : true
bridge.indexOf(1); // 1이 있는 index return 없으면 -1 return
2. Queue 메소드의 종류

문제

ArrayList를 이용해서 풀었을 때
  1. 현 상황을 보기 쉬웠다.
  2. 코드의 조건과 길이가 길어진다.
Queue를 이용해서 풀었을 때

1.지웠다 추가를 안해도 된다. 2.코드가 간결하다 3.head와 tail만 건들 수 있다.

제네릭부분은 블로그 참고를 많이 했다. 제네릭관련 블로그 가기

참고