[프로그래머스/자바] 다리를 지나는 트럭 풀이

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

프로그래머스

 

프로그래머스 코딩테스트 고득점 Kit의 스택/큐 Level 2 문제다.

 

 

 

현재 다리를 건너고 있는 트럭들을 저장하기 위한 LinkedList를 생성해

트럭이 다리에 들어올 때마다 list에 넣는다.

List에 있는 모든 Bridge의 시간을 1초씩 더해 다리를 건너도록 해야 하므로

인덱스로 접근이 가능한 LinkedList를 사용했다.

 

List 가장 위에 있는 원소가 가장 처음으로 들어간 트럭,

즉 가장 빨리 다리를 빠져나올 트럭이므로

가장 위에 있는 원소의 sec만 체크하여 bridge_length와 같다면 

list에서 빼내고 nowWeight, nowLen를 수정한다.

 

 

간단한 문제인데 여러 동작들을 어떤 순서로 해야할지 감이 안 잡혀 꽤 헤맸다.

선형 구조로 되어있고 시간에 따라 처리하는 문제에 약한 것 같다..

import java.util.*;

class Solution {
    public int solution(int bridge_length, int weight, int[] truck_weights) {
		LinkedList<Bridge> list = new LinkedList<>();

		int sec = 1; 
		int idx = 0; // truck_weights 배열 인덱스
		int cnt = 0; // 다리를 지난 트럭의 갯수 카운트
		int nowWeight = 0; // 현재 다리의 weight
		int nowLen = 0; // 현재 다리의 트럭 갯수

		while(cnt < truck_weights.length) {
			if(!list.isEmpty() && list.peek().sec == bridge_length) { // 다리 지나기
				nowWeight -= list.poll().weight;
				nowLen--;
				cnt++;
			}
			
			for(Bridge b : list) // 1초씩 다리 건너기
				b.addSec();
			
			if(idx < truck_weights.length 
					&& nowWeight + truck_weights[idx] <= weight 
					&& nowLen + 1 <= bridge_length) { // 다리에 트럭 추가
				nowWeight += truck_weights[idx];
				nowLen++;
				list.add(new Bridge(truck_weights[idx++]));
			}
			sec++;
		}

		return sec - 1;
    }
    
    class Bridge {
		int sec = 1;
		int weight;

		public Bridge(int weight) {
			this.weight = weight;
		}

		public void addSec() {
			this.sec++;
		}
    }
}