칸비

개발 찍어먹기

[Programmers]-다리를 지나는 트럭(스택/큐)

문제

저는 다리를 기준으로 다리 건너기 전 다리 다리 건넌후 상황을 배열로 표현해서 풀었다.

맨밑 주석을 풀어 while문에 넣으면 상황을 볼수있다. 다른사람들은 큐 링크드리스트를 이용했다. 자료구조를 좀 알아봐야겠네.

import java.util.ArrayList;

class Solution {
    public int solution(int bridge_length, int weight, int[] truck_weights) {
        int answer = 0;   
        int weight_sum = 0;       
        int time = 0;
        
        ArrayList<Integer> before_bridge = new ArrayList<Integer>();//다리 건너기 전 상황 arraylist
        for(int i=0;i<truck_weights.length;i++) before_bridge.add(0, truck_weights[i]);
        
        ArrayList<Integer> bridge = new ArrayList<Integer>();//다리 상황
        for(int i=0;i<bridge_length;i++) bridge.add(0);// 0 초기화
        
        ArrayList<Integer> after_bridge = new ArrayList<Integer>();//다리 건넌 후 상황 arraylist 
        
        while(true){
            
            if(bridge.get(bridge.size()-1)!=0)//다리에 0이 아니면
            after_bridge.add(0, bridge.get(bridge.size()-1));// 다리 > 후 트럭 옮기기        
            bridge.remove(bridge.size()-1);
            
            for(int i=0;i<bridge.size();i++) weight_sum+=bridge.get(i);
            
            if(before_bridge.size()>=1){//전 트럭 유무확인
                       
                if(weight_sum+before_bridge.get(before_bridge.size()-1)<=weight){//무게 조건
                    bridge.add(0, before_bridge.get(before_bridge.size()-1));// 전 > 다리 트럭 옮기기
                    before_bridge.remove(before_bridge.size()-1);
                }
                else bridge.add(0,0);
                
                weight_sum=0;//0초기화
            }       
            else bridge.add(0,0);
            
            time++;
            if(after_bridge.size()==truck_weights.length) {//트럭 수 비교로 while탈출
                answer = time;
                break;
            }
        }
            
        /*for(int i=0;i<before_bridge.size();i++) System.out.print(before_bridge.get(i)+" ");
        System.out.println();
        for(int i=0;i<bridge.size();i++) System.out.print(bridge.get(i)+" ");
        System.out.println();
        for(int i=0;i<after_bridge.size();i++) System.out.print(after_bridge.get(i)+" ");
        System.out.println();*/

        return answer;
    }
}

블로그에 사진 넣는 방법

  1. .github.io/assets/images 에 이미지를 넣어 논다.
  2. 마크다운에 ![제목](/assets/images/aaa.png) 를 작성한다.
  3. 작성한 파일이름이랑 확장자명을 확인(대소문자도 확인)한다.

다시풀기

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

class Solution {
    public int solution(int bridge_length, int weight, int[] truck_weights) {
        
        Queue<Integer> q = new LinkedList<Integer>();//다리 큐
        for(int i=0;i<bridge_length;i++){
            q.offer(0);
        }
        
        Queue<Integer> wait = new LinkedList<Integer>();//대기트럭 큐
        for(int i=0;i<truck_weights.length;i++){
            wait.offer(truck_weights[i]);
        }
        
        int total_weight = 0;//다리 무게
        int count = 0;//시간
        while(!wait.isEmpty()){//대기트럭 비면 종료
            count++;
            int output = q.poll();
            if(output != 0) total_weight -= output;
            
            if(wait.peek() + total_weight > weight ) q.offer(0);//무게넘으면
            else {//안넘으면
                int input = wait.poll();
                q.offer(input);
                total_weight += input;
            }
        }
        return count+bridge_length;
    }
}

요약

주석처리로 깔끔해졌다.

두개의 큐를 이용해서 대기큐, 다리큐를 컨트롤했다.

주석도 깔끔히.

참고