[Java] 프로그래머스 : 다리를 지나는 트럭[Queue]

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

프로그래머스

혼자 머리를 굴리다 결국 블로그들 코드 참고...

 

 

 

문제

 

 

 ·  9번 줄 : 처음엔 priorityQueue<Integer> queue = new priorityQueue<>();와 같이 작성하였으나 테스트1번이

       10초동안 결과를 내지 못해 오답처리가 되어 LinkedList로 바꾸어 주었다. 

LinkedList - 자료들을 반드시 연속적으로 배열시키지 않고 임의의 공간에 저장한 후, 순서에 따라 서로 연결시킨 구조

                   노드의 삽입, 삭제 작업이 용이

PriorityQueue - 각 데이터가 우선순위를 갖고 있어 우선순위가 높은 순서대로 나오게 해주는 큐

                         저장공간으로 배열을 사용하며, 각 요소를 힙(heap)이라는 자료구조의 형태로 저장

 

 ·  13번 줄 : Queue(다리)가 비어있는 경우, queue에 truck을 넣어주고, sum에 truck의 무게를 추가, time++을 해준다.

 ·  18번 줄 : Queue(다리)가 트럭으로 가득 찬 경우, 큐에서 트럭을 하나 제거해준다.

         (가장 먼저 들어간 트럭을 제거해주고 트럭을 새로 넣는 기능까진 넣지 않았으므로 time++은 해주지 않았다.)

 ·  20번 줄 : 그 외

         21번 줄 : 새로운 트럭을 다리에 올려주려는데 기존에 있던 트럭과의 무게가 weight를 초과하면

              queue에 truck대신 0을 추가해주고 time++해준다.

         24번 줄 : 추가되는 트럭의 무게의 합이 weight 미만일 때,

              queue에 truck을 추가,  sum에 truck무게 추가, time++해준다. 

 ·  33번 줄 : 마지막 트럭의 다리 통과 시간을 더해줌

 

import java.util.*;

class Solution {
    public int solution(int bridge_length, int weight, int[] truck_weights) {
        int answer = 0;
        int time = 0;
        int sum = 0;

        Queue<Integer> queue = new LinkedList<Integer>();

        for(int truck : truck_weights) {
            while(true) {
                if(queue.isEmpty()) {
                    queue.offer(truck);
                    sum += truck;
                    time++;
                    break;
                }else if(queue.size() == bridge_length){
                    sum -= queue.poll();
                }else{
                    if(sum + truck > weight) {
                        queue.offer(0);
                        time++;
                    }else {
                        queue.offer(truck);
                        sum += truck;
                        time++;
                        break;
                    }
                }
            }
        }
        answer = time + bridge_length;

        return answer;
	}
}

 

 

프로그래머스에 작성된 코드

클래스 사용

mport java.util.*;

class Solution {
    class Truck {
        int weight;
        int move;

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

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

    public int solution(int bridgeLength, int weight, int[] truckWeights) {
        Queue<Truck> waitQ = new LinkedList<>();
        Queue<Truck> moveQ = new LinkedList<>();

        for (int t : truckWeights) {
            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 > bridgeLength) {
                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;
    }
}

 

 

stack과 map을 이용하며 하나씩 지워나가며 결과 도출

import java.util.HashMap;
import java.util.Map;
import java.util.Stack;

class Solution {
    public int solution(int bridge_length, int weight, int[] truck_weights) {
            Stack<Integer> truckStack = new Stack<>();
            Map<Integer, Integer> bridgeMap = new HashMap<>();

            for (int i = truck_weights.length-1; i >= 0; i--)
                truckStack.push(truck_weights[i]);

            int answer = 0;
            int sum = 0;
            while(true) {
                answer++;

                if (bridgeMap.containsKey(answer))
                    bridgeMap.remove(answer);

                sum = bridgeMap.values().stream().mapToInt(Number::intValue).sum();

                if (!truckStack.isEmpty())
                    if (sum + truckStack.peek() <= weight)
                        bridgeMap.put(answer + bridge_length, truckStack.pop());

                if (bridgeMap.isEmpty() && truckStack.isEmpty())
                    break;


            }
            return answer;
    }
}

 ·  18번 줄 : Map에 answer++해준 숫자의 Key값을 찾고, 있을 경우 제거

 ·  21번 줄 :

         bridgeMap.values() - Map의  값

         .stream() - 출력 메소드

         .mapToInt(Number::intValue).sum() - value값들을 더해주기 위해 Integer를 Int로 변환해주는 메소드

 ·  23번 줄 : stack이 비어있지 않은 경우, map의 값들의 합과 stack의 맨위의 값의 합이 weight보다 작으면

          Map에 answer + 다리의 길이를 Key로 넣어주고 stack의 맨 위 값을 제거해준다. 

 ·  27번 줄 : Map과 Stack이 모두 비어있으면 While문을 종료시켜준다.