Truck

2회차 풀이 틀린 이유

일단 큐에 트럭 넣을 때와 큐에서 트럭 뺄 때 2가지 경우로 나누어 생각해봤다. 1. 큐에 트럭 뺄 때 : 큐의 크기가 w(다리의 길이)와 같을 때 => 트럭의 무게 때문에 트럭이 하나만 들어가있을 때도 이동을 하지만, 조건을 위처럼 걸어주게 되면 큐에서 트럭이 나오지 않고 무한반복문으로 돌아버린다. 문제에서 하나의 단위시간에 하나의 단위길이만큼 이동한다고 했으니까 시간'2' 동안 거리'2'를 이동한다고 할 수 있다. 다시 말하면, 큐에 트럭을 넣을 때 시간을 큐에 함께 넣어서 기록해주고, 현재의 시간에서 큐의 제일 처음 트럭의 . 시간의 차가 w(다리 길이)와 같다면 그 시간 차만큼 거리도 이동한 것이기 때문에 아래와 같이 구현하면 된다.

//큐에서 다리 뺄 때.
if(time-q.peek()[1] == w) {
  weight -= q.remove()[0];
}

2. 큐에 트럭 넣을 때 조건 - 넣을 트럭의 인덱스 idx < n - 넣을 트럭 무게 + 현재 다리 위 트럭 무게 합 <= L - 현재 큐의 크기와 다리 길이 비교

인덱스 범위 만족, 무게 합 조건 만족해도 아래와 같은 경우라면 트럭 넣을 수 없다! ex) n = 3, w = 2, L = 3 : 현재 다리 11인경우 현재 큐의 크기 == w이기 때문에 더 이상 트럭 넣을 수 없다.

그런데 큐 크기 비교조건을 넣어주지 않아도 1번(시간차 이용)에서 큐에서 트럭을 뺄 것이기 때문에 문제에서 요구하는 정답을 도출해낼 수 있다.

if(q.size()<w && idx<n && weight+t[idx]<=l) {//큐의 크기도 w보다 작아야하는 조건. 현재 큐에 11이 들어있고 L은 3이지만 w가 2라면 더이상 들어갈 수 없기 때문이다!
  q.add(new int[] {t[idx],time});
  weight += t[idx];
	idx++;
}

알고리즘 생각

1. 큐에 트럭 넣는다.

0번째 트럭이 L보다 작으면 큐에 넣는다. i-for문을 돌리며 i번째 트럭 + q.peek() <= L이면 큐에 넣는다. (=> 틀린 부분 : 트럭 값의 합이 L보다 작으면 트럭을 계속 넣을 수 있어야한다!) (트럭을 넣으면서도 time은 계속 증가)

2. 큐 사이즈가 W가 되면 제일 앞의 트럭부터 꺼내고 time 증가시켜준다.

수정

1번을 보완하기 위해 큐에 들어간 트럭값의 합을 sum에 저장해주고, sum이 L보다 작다면 i번째 트럭을 큐에 넣고, L보다 크면 i-1번째까지만 넣어준다. 지금 다시 생각해보니 i번째까지 트럭값 합이 L 초과하면 그냥 안 더해주면 되는데! =>if(i-1>=0)문 삭제해야할듯.

for(int i=0;i<n;i++) {
			sum += truck[i];
			if(sum <= l) {
				q.add(truck[i]);time++;
			} else {//i-1까지 트럭만 넣는다!
				if(i-1>=0) {
					q.add(truck[i-1]);time++;
				}
			}
			//time = time+w+q.size();
			if(q.size()==w) {
				while(!q.isEmpty()) {
					q.remove();
					//time++;
					time = time+q.size();
				}
			}
		}

Solution

1. 큐에 넣을 트럭 idx를 기록한다. 처음에 0번째 트럭을 넣기 때문에 idx는 1부터 시작한다.

2. 큐에서 뺄 때 = 현재의 시간 time-큐 제일 첫 트럭의 시간값 = w일 때 = 현재 시간과 큐의 첫 트럭이 큐에 들어간 시간차가 w이면 그 트럭은 나온다! = 트럭이 나오는 것은 L값을 가감해서 처리할 수 있다! L = L + q.peek()[0]

3. 걸리는 시간 계산 1번과 2번(트럭을 넣을 때, 뺄때)을 반복문으로 구성하고, 반복문을 한번 돌 때마다 time을 1씩 증가시켜준다. 큐가 비지 않을동안만 반복한다.(while(!q.isEmpty)