다리를 지나는 트럭

프로그래머스에서 제공하는 문제들 중 큐를 연습하기 위한 문제를 풀었다.

문제 링크 : https://programmers.co.kr/learn/courses/30/lessons/42583

코딩테스트 연습 - 다리를 지나는 트럭 | 프로그래머스

 

문제 설명

문제설명 및 예시

---

풀이 과정

큐와 연결 리스트를 활용해 문제를 해결하려 했다. 이 때 발견해낸 문제가 각 트럭당 현재 상태를 확인하는 것에 대한 것이였다. 어떻게 각 트럭당 건넌 상태를 확인할 지에 대해 정확히 어떻게 큐로 구현할 지 감이 잘 오지 않았다.

여러 모로 생각해본 후 일단은 큐를 활용해 구현하기로 했던 처음 생각을 고수하기로 했다.

트럭이 다리에 들어가게 되면 점점 무게에 제한을 주어 더 이상 트럭이 들어가지 않고 대기해야 한다. 이는 잠시 생각해본 후 금새 해결할 수 있었다. 하지만 트럭들은 한 번에 다리에 들어갈 수 없기 때문에 각 트럭들의 진입 시간을 저장해두어 다리에서 빠져나간 시간을 알 수 있도록 해야 했다. 이 방법에 대해서는 큐를 활용해 정확히 어떤 방식으로 구현을 시도해야 할 지 고민이 많이 되었던 부분이었다.

한동안 여러 방면으로 고심해본 끝에 진입 당시의 시간값과 다리 길이값을 함께 더한 값을 추가적인 배열에 저장하는 방법을 통한다면 트럭들의 서로 다른 통과시간을 파악할 수 있을 것이라는 결론이 났다.

오류. 확인 결과 weight와 sum이 일치할 경우를 제외해 발생한 문제였다.

---

...

	if (sum + truckWeights[truckNum] < weight) {
		cross.offer(truckWeights[truckNum]);
		sum += truckWeights[truckNum];
		timer[truckNum++] = time + bridgeLength;
	}
    
...

 

생각했던 대로 코드를 작성한 후 테스트를 진행했을 때 예상과는 다르게 마지막 테스트의 결과가 201로 110과는 크게 차이가 발생했다.

원인을 찾아본 후 위 코드 부분에서 트럭의 총 무게가 다리의 무게 제한과 같을 경우 다음 트럭을 투입시켜야 하는데 해당 경우를 넣어주지 않아 발생한 문제였다는 것을 발견해냈다.

...

int[] timer = new int[truckWeights.length]; //트럭들의 통과 예정시간을 저장

...

	if (truckNum < truckWeights.length) {
		if (sum + truckWeights[truckNum] <= weight) {
			cross.offer(truckWeights[truckNum]);
			sum += truckWeights[truckNum];
			timer[truckNum++] = time + bridgeLength;
		}
	}
	
	if (timer[truckWeights.length - 1] != 0)
		break;
           
...

 

결론적으로는 다리에서 트럭 하나가 빠져나갈 때마다 해당 트럭의 무게만큼을 총 무게 합에서 빼주며 최종적으로 마지막 배열 인덱스에 값이 들어갈 경우 반복을 빠져나가도록 하며 해당 트럭이 나갈 시간을 반환하도록 만들어주어 문제를 해결하게 되었다.

 

최종 코드

package StackQueueProblem;

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class TruckPassingBridge {
	public static void main(String[] args) {
		init();
	}
	
	static void init() {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
			
		try {
			int bridgeLength = Integer.parseInt(br.readLine());
			int bridgeWeight = Integer.parseInt(br.readLine());
			String truckInput = br.readLine();
			StringTokenizer st = new StringTokenizer(truckInput);
			int index = 0;
			int[] truckWeights = new int[st.countTokens()];
			
			while (st.hasMoreTokens())
				truckWeights[index++] = Integer.parseInt(st.nextToken());
			
			bw.write(String.valueOf(solution(bridgeLength, bridgeWeight, truckWeights)));
			bw.close();
		} catch (IOException e) {
			e.printStackTrace();
		}
	}
	
	static int solution(int bridgeLength, int weight, int[] truckWeights) {
		int time = 0, truckNum = 0, sum = 0, index = 0;
		Queue<Integer> cross = new LinkedList<>();
		int[] timer = new int[truckWeights.length];
		
		while (true) {
			time++;
			
			if (timer[index] == time) {
				sum -= cross.peek();
				cross.poll();
				index++;
			}
			
			if (truckNum < truckWeights.length) {
				if (sum + truckWeights[truckNum] <= weight) {
					cross.offer(truckWeights[truckNum]);
					sum += truckWeights[truckNum];
					timer[truckNum++] = time + bridgeLength;
				}
			}
			
			if (timer[truckWeights.length - 1] != 0)
				break;
		}
		
		return timer[truckWeights.length - 1];
	}
}

---

 

채점 결과