[프로그래머스] 다리를 지나는 트럭 (Java 자바)

문제

https://programmers.co.kr/learn/courses/30/lessons/42583?language=java 

코딩테스트 연습 - 다리를 지나는 트럭

 

풀이 및 소스코드

 

하 이 문제는 풀 때마다 어렵고 풀기가 싫다.

고려해줘야할 조건이 많아서 그런 것 같다.

머리가 안돌아가.. ~~

 

파이썬으로 할 때는 answer을 0부터 시작해도 맞는 답이 나왔는데, 자바로 푸니 1씩 적게 나와서 애초에 answer을 1로 초기화 시켜놓고 풀었더니 pass 할 수 있었다.

 

cross : 다리를 지나고 있는 트럭

pass : 다리를 건넌 트럭

time : 다리를 지나고 있는 트럭들에 대한 경과 시간이 담긴 ArrayList

time을 사용한 이유는 시간이 흐를 때 마다 +1씩 해줘야했기 때문이다.

(파이썬은 큐의 요소도 수정할 수 있는데 자바는 안되나보다.)

 

먼저 cross와 sum에 첫번째 트럭의 무게를 담고, time에는 0을 넣는다.

(마찬가지로 파이썬에는 큐의 합을 계산하는 sum 함수가 있는데 자바는 없... 읍ㄷ읍.. 큐에 들어오면 일일히 더해주고 pop하면 빼줘야한다.)

 

[time의 기능]

다리가 버틸 수 있는 무게가 총 10이며, 길이가 2인 다리에 진입한다고 하자.

무게 5인 트럭 진입

time : [0]

무게 3인 트럭 진입과 동시에 1초의 시간이 흐름.

time : [1, 0]

무게 2인 트럭 진입 하려고 했으나, 길이 2인 다리 꽉 참. 1초의 시간만 흐른다.

time : [2, 1]

2초가 지나 맨 처음 진입한 트럭 다리 통과 완료. time.pop();

time : [1]

 

지나간 트럭이 n보다 같아지기 전까지 while 문을 돌린다. 

 

먼저, while문이 시작될 때 현재 다리를 지나는 트럭에 대한 시간을 +1 해준다. 그리고 answer 에도 +1을 해준다.

시간이 1 흘렀음을 의미한다.

 

그렇게 증가된 time 의 첫번째 요소( 즉, 제일 먼저 들어온 트럭에 대한 경과시간 )가 다리의 길이(bridge_length)와 같아지면 다리에서 내려오게 되므로, cross에서 pop해주고 pass에 add 해준다. 또한 다리에 있는 트럭이 하나 빠졌으므로 다리 위에 있는 트럭들 무게의 총합을 담고있는 sum에서 그 값만큼 빼준다.

 

그리고 다음 트럭을 올릴 수 있는지 여부도 따져봐야 한다.

만약 제일 최근에 다리에 올린 트럭의 idx 값이 nowidx 라면 nowidx+1 번째가 존재하는 지 보고,

존재한다면 sum에 그 트럭의 무게를 더해도 다리가 버틸 수 있는 weigth 보다 같거나 작은지 확인한다.

만약 작거나 같다면 cross에 다리를 추가하고, time에 0이라는 시간을 추가하고, sum에 그 무게를 추가하고, nowidx = nowidx+1을 해준다.

이렇게 반복하다보면 트럭들이 다리를 전부 지나게 되고, while문이 끝나게 된다.

 

import java.util.*;

class Solution {
	public static int solution(int bridge_length, int weight, int[] truck_weights) {
		int answer =1;
		Queue<Integer> cross = new LinkedList<Integer>();
		Queue<Integer> pass = new LinkedList<Integer>();
		ArrayList<Integer> time = new ArrayList<Integer>();
		int n= truck_weights.length;
		cross.add(truck_weights[0]);
		time.add(0);
		int nowidx = 0;
		int sum = truck_weights[0];
		while(pass.size()<n) {
			int time_n = time.size();
			for(int i=0;i<time_n;i++) time.set(i, time.get(i)+1);
			answer ++;
			if(time.get(0)==bridge_length) {
				int byetruck = cross.remove();
				pass.add(byetruck);
				time.remove(0);
				sum -= byetruck;
			}
			if(nowidx+1 <n ) {//고려할 트럭이 더 있으면!
				if(sum+truck_weights[nowidx+1]<=weight) {
					cross.add(truck_weights[nowidx+1]);
					time.add(0);
					sum += truck_weights[nowidx+1];
					nowidx += 1;
				}
			}
		}
		return answer;
	}
	public static void main(String[] args) {
		int b = 100;
		int w = 100;
		int[] t = {10};
		System.out.println(solution(b, w, t));

	}

}