[백준 | 13335] 트럭 - Java(Linked List 사용)
문제
강을 가로지르는 하나의 차선으로 된 다리가 하나 있다. 이 다리를 n 개의 트럭이 건너가려고 한다. 트럭의 순서는 바꿀 수 없으며, 트럭의 무게는 서로 같지 않을 수 있다. 다리 위에는 단지 w 대의 트럭만 동시에 올라갈 수 있다. 다리의 길이는 w 단위길이(unit distance)이며, 각 트럭들은 하나의 단위시간(unit time)에 하나의 단위길이만큼만 이동할 수 있다고 가정한다. 동시에 다리 위에 올라가 있는 트럭들의 무게의 합은 다리의 최대하중인 L보다 작거나 같아야 한다. 참고로, 다리 위에 완전히 올라가지 못한 트럭의 무게는 다리 위의 트럭들의 무게의 합을 계산할 때 포함하지 않는다고 가정한다.
예를 들어, 다리의 길이 w는 2, 다리의 최대하중 L은 10, 다리를 건너려는 트럭이 트럭의 무게가 [7, 4, 5, 6]인 순서대로 다리를 오른쪽에서 왼쪽으로 건넌다고 하자. 이 경우 모든 트럭이 다리를 건너는 최단시간은 아래의 그림에서 보는 것과 같이 8 이다.
다리의 길이와 다리의 최대하중, 그리고 다리를 건너려는 트럭들의 무게가 순서대로 주어졌을 때, 모든 트럭이 다리를 건너는 최단시간을 구하는 프로그램을 작성하라.
입력
입력 데이터는 표준입력을 사용한다. 입력은 두 줄로 이루어진다. 입력의 첫 번째 줄에는 세 개의 정수 n (1 ≤ n ≤ 1,000) , w (1 ≤ w ≤ 100) and L (10 ≤ L ≤ 1,000)이 주어지는데, n은 다리를 건너는 트럭의 수, w는 다리의 길이, 그리고 L은 다리의 최대하중을 나타낸다. 입력의 두 번째 줄에는 n개의 정수 a1, a2, ⋯ , an (1 ≤ ai ≤ 10)가 주어지는데, ai는 i번째 트럭의 무게를 나타낸다.
출력
출력은 표준출력을 사용한다. 모든 트럭들이 다리를 건너는 최단시간을 출력하라.
예제 입력
내 제출
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.LinkedList;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
String[] input = br.readLine().split(" ");
int N = Integer.parseInt(input[0]);
int W = Integer.parseInt(input[1]);
int L = Integer.parseInt(input[2]);
LinkedList<Integer> trucks = new LinkedList<>();
String[] trucksWeight = br.readLine().split(" ");
for (int i = 0; i < N; i++) {
trucks.add(Integer.parseInt(trucksWeight[i]));
}
LinkedList<Integer> bridge = new LinkedList<>();
for (int i = 0; i < W; i++) {
bridge.add(0);
}
int currentWeight = 0;
int time = 0;
while (!bridge.isEmpty()) {
time++;
currentWeight -= bridge.pollFirst();
if (!trucks.isEmpty()) {
if (currentWeight + trucks.peekFirst() <= L) {
currentWeight += trucks.peekFirst();
bridge.addLast(trucks.pollFirst());
} else {
bridge.add(0);
}
}
}
br.close();
bw.write(time+"");
bw.flush();
bw.close();
}
}문제 해결 사고 과정
문제 이해
이 문제는 트럭들이 주어진 조건(다리의 길이와 최대 하중) 하에서 다리를 건너는 데 걸리는 최단 시간을 계산하는 것입니다. 다리 위에 동시에 올라갈 수 있는 트럭의 수와 이들의 무게가 제한되기 때문에, 이를 고려하여 트럭들의 이동을 시뮬레이션해야 합니다.
접근 방식
먼저 트럭들이 다리를 건너는동안 동안 다리 위에 있는 트럭의 상태를 관리하기 위하여 리스트를 연선언해주었고. 다리의 길이 `W`의 맞게 초기 상태로 `W`개의 0(빈 자리)를 리스트에 채워두었습니다.
그 후 매 초마다 다리 위에 있는 트럭들을 한 칸씩 전진 시켜주었습니다. 이때 리스트의 첫번째 요소에 있는 값을 제거하여 트럭이 다리를 빠져나갔음을 표시하고 현재 다리 무게의 총 무게에서 해당 트럭의 무게를 빼주었습니다.
그 후 새로 다리에 진입할 수 있는 트럭이 있는지 확인하고 현재 다리위의 총 무게와 새 트럭의 무게의 합이 최대 하중을 초과하는지 검사하였습니다. 조건이 만족되면 트럭을 다리 위에 올리고 리스트의 마지막에 트럭의 무게를 추가하였습니다. 만약 조건이 만족하지 않으면 0을 추가하여 빈자리를 채워주었습니다.
자료 구조 선택 이유
선택한 자료 구조
LinkedList
이유 및 장점
연결 리스트는 배열의 처음과 끝에서 데이터를 삽입 추가할 수 있고 처음이나 끝에서 삽입 및 삭제가 O(1)의 시간 복잡도로 매우 효율적이라고 생각하여 사용하였습니다.
시간 및 공간 복잡도 분석
시간 복잡도
트럭은 순서대로 다리를 건너며, 각 트럭이 다리를 완전히 건너는 데 걸리는 시간은 다리의 길이 W와 트럭의 수 N에 의존합니다.각 트럭이 다리를 건너기 위해 최소 W만큼의 시간이 필요하며, 모든 트럭이 다리를 건너야 하기 때문에 전체적으로 O(N * W)의 시간이 걸립니다. 매 초마다 트럭을 다리에서 내리고 새로운 트럭을 다리에 올리는 작업은 모두 O(1)입니다. 따라서, 매 초마다 이루어지는 작업은 전체적으로 O(N * W)입니다.
공간 복잡도
다리의 상태를 나타내는 `bridge` 리스트는 다리의 길이 `W`만큼의 공간을 사용합니다. 따라서, bridge의 공간 복잡도는 O(W)입니다. 또한, 트럭의 수 `N`만큼의 초기 입력을 저장하는 `trucks` 리스트도 존재하지만, 이 리스트는 점차 비워지므로 전체적으로 O(N)의 공간을 필요로 합니다.