[JAVA] 13335번 - 트럭
문제 탐색하기
- 문제에서 구해야 하는 최종 정답은 무엇인지 탐색한 과정
- 그 정답을 구하기 위해 어떻게 코드를 구현해야 할지 고민한 과정
- 문제에 들어오는 범위를 파악하여 어떤 알고리즘을 쓸 수 있을지 고민해 가는 과정
다리에 입장해서 다리를 빠져나가야하니까 큐를 이용하면 된다.
트럭이 다리에 진입하면 큐에 추가하고, 다리에서 나가면 큐에서 제거한다.
1. 다리와 트럭
트럭의 리스트를 큐로 관리하고(트럭이 다리에 순서대로 올라가야하니까)
다리 큐를 만들어 다리 위의 트럭을 관리하면 된다.
2. 시간관리
트럭이 다리를 건너는 시간을 time으로 관리한다
매 시간마다 다리에서 트럭이 이동하고, 새로운 트럭이 다리에 올라갈 수 있는지를 판단해야한다
3. 조건처리
매 시간마다, 다리 위에서 트럭이 한 칸 앞으로 이동, 다리를 벗어난 트럭이 있으면 제거
새 트럭이 다리에 올라갈 수 있는지(하중 초과하지않는지 확인한다
다리의 길이 제한에 따라 동시에 올라갈 수 있는 트럭의 수를 관리한다
시간복잡도
트럭이 트럭위에서 다리의 길이 w만큼 이동을 해야한다
트럭 n대가 각각 w번 다리를 이동해야하니가
O(n*w)이다.
n은 최대 1,000이고 w는 최대 100이니까 O(100,000)으로 1초안에 충분히 가능하다
코드 설계하기
위의 문제 탐색하기에서 고민한 과정을 토대로 문제 풀이에 대한 실마리를 잡았다면, 문제 풀이를 본격적으로 하기전, 문제를 풀이 위한 로드맵을 그려본다
어떤 순서로 코드를 작성해야 할지, 어떤 함수들을 작성해야 할지 등을 작성
1.트럭과 다리 큐를 설정한다, 초기에는 다리의 길이 w만큼 0으로 채운다(트럭이 없으니까)
<시간에 따른 트럭 이동처리>
2. 시간을 1씩 증가시키면서, 다리 위 트럭들이 한 칸씩 앞으로 이동하고, 새로운 트럭 다리에올림(무게 안넘게)
3. 다리에서 트럭이 나가면 무게 갱신
-> 모든 트럭이 다리를 건널 때까지 반복한다.
시도 회차 수정 사항
- 무분별하게 "맞았습니다" 가 나올때까지 수정하는 형태의 문제 풀이를 반복하면, 내가 어떤 실수를 해서 해당 문제를 틀렸는지 모르게 된다
- 틀렸습니다를 받았다면 왜 틀렸는지 고민핸보고, 어떻게 수정할 수 있는지 고민하는 과정을 작성
- 위에 내가 세울 설계에서 어떤 부분이 틀렸는지도 함께 점검
1회차 시도
문제점
다리 위의 트럭이 다리의 길이만큼 머물러야 하는 상황이 구현되지 않음
예를 들면 다리 길이가 100이면 100만큼 소비되어야 다리를 건넌건데 이걸 고려 못함
트럭이 다리에 올라갈 때, 현재 다리 위의 트럭들의 무게 합을 계산하여 하중 확인해야하는데 , 내 코드는 무게 계산이 올라간 즉시 계산되지만, 다리 위에서 머물러 있는 시간 동아느이 무게 관리를 고려안함
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Comparator;
import java.util.Deque;
import java.util.HashMap;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;
import java.util.Queue;
import java.util.Set;
import java.util.StringTokenizer;
import java.util.TreeSet;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
int n = Integer.parseInt(st.nextToken());
int w = Integer.parseInt(st.nextToken());
int L = Integer.parseInt(st.nextToken());
int [] arr = new int[n];
st = new StringTokenizer(br.readLine());
for(int i=0; i<n; i++) {
arr[i] = Integer.parseInt(st.nextToken());
}
int cnt=0;
Deque<Integer> q = new ArrayDeque<>();
for(int i=0; i<arr.length; i++) {
int sum=0;
q.offer(arr[i]); // 1. 큐에 숫자 삽입
for(Integer k : q) {
sum+=k;
}
if(sum<=L) {
System.out.println("하중초과안함"+sum);
cnt++;
}
else if(sum>L) { // 무게하중을 초과한다면
System.out.println("하중초과함"+sum);
q.removeLast(); // 방금 넣은 숫자 제거
cnt++;
q.poll(); // 맨 앞 숫자 큐에서 제거
}
}
System.out.println(cnt);
\
}
}
정답 코드
다 뜯어고쳣다
ㄴㅏ는 구현이 제일어렵다..ㅋㅋ
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
int n = Integer.parseInt(st.nextToken());
int w = Integer.parseInt(st.nextToken());
int L = Integer.parseInt(st.nextToken());
Queue<Integer> bridge = new LinkedList<>();
Queue<Integer> truck = new LinkedList<>();
st = new StringTokenizer(br.readLine());
for(int i=0; i<n; i++) {
truck.add(Integer.parseInt(st.nextToken()));
}
for (int i = 0; i < w; i++) {
bridge.add(0);
}
int time=0;
int currentBridgeWeight = 0;
//모든 트럭이 다리를 다 건널떄까지 반복
while(!bridge.isEmpty()) {
time++;
//다리에서 트럭 빠져나가면 그 무게는 뺀다
currentBridgeWeight -= bridge.poll();
if(!truck.isEmpty()) {
if(currentBridgeWeight+truck.peek() <=L) {
int tmp = truck.poll();
bridge.offer(tmp); //트럭이 다리에 진입
currentBridgeWeight+=tmp; //무게 갱신
}
else {
bridge.offer(0);
}
}
}
System.out.println(time);
}
}