트럭

자료구조 : 큐

틀린 이유

1. 트럭이 다리 위에 올라갈 때 조건으로 해당 트럭의 무게만 L과 비교했었는데 그게 아니라 다리 위에 올라간 모든 트럭 무게의 합과 L을 비교해야한다.

2. 반복조건 : 생각하는 것에 따라 while(!q.isEmpty()) 또는 while(count<N) //다리 통과 트럭갯수가 될 수 있다. 반복조건이나 트럭 승차 하차 조건 판단을 위한 시간 저장 방법 같은 것들은 얼맏든지 다양하게 구현할 수 있다. 중요한 것은 로직을 꼼꼼하게 구현하는 것이다!!!!

반복 조건 생각 발전시킨 순서

1. 다음으로 다리에 올라가는 트럭 인덱스로 반복문 idx번째 트럭이 탑승 조건에 부합하지 못하여 탑승을 못했음에도 불구하고 idx가 증가해버리게 된다! 문제 예시에서는 7트럭이 올라가고, 4트럭은 탑승하지 못하고 기다려야한다. 하지만 트럭의 idx로 반복문을 만들면 4트럭은 탑승 못했음에도 불구하고 idx가 증가하여 다음 트럭인 5트럭이 탑승할 차례가 되버리는 것이다. 따라서 알맞은 반복문이 될 수 없다.

2. 트럭 탑승 조건에 부합하여 트럭이 다리 위에 올라가면, idx+1로 증가하여 다음 트럭을 올릴지 말지 결정하고 그에 따른 연산을 할 수 있다! 따라서, 트럭 탑승 조건 if문 내에서 idx를 1씩 증가시킨다!!!

3. 종료 조건 : idx == N-1 이고, 큐가 비어있으면 모든 마지막인 N-1번째 트럭까지 이동을 완료한 것이다. 따라서, 탑승 조건에도 idx가 N보다 작아야하기 때문에 이 조건을 검사해줘야한다. if(idx >N-1) continue;로 처리했었는데 이보다는 if(idx < N && sum +Truck[idx] <= L) 로 다리에 올라가는 하중 조건과 AND 연산으로 함께 구현해주는 것이 더 간결했다.

생각하지 못한 부분

1. 다리 위에 idx번째 트럭이 올라갈 수 있는지 조건 검사 idx번째 트럭의 무게(Truck[id]) 뿐만 아니라 현재 다리 위의 트럭들의 무게합에 합산한 값을 다리 최대 하중(L)과 비교해야 한다!⭐️⭐️⭐️⭐️⭐️ 현재 탑승할 트럭 무게는 10 이고 다리 위 트럭들 무게는 90, L = 95일 때, 트럭은 탑승하지 못하지만, idx번째 트럭의 무게 10으로 L과 검사하면 틀린 조건 판단이 된다!

2. 반복 조건 : while(!q.isEmpty())⭐️⭐️⭐️⭐️⭐️ 코드 구현 순서 수정 코드에서 트럭을 먼저 올리고(큐에 삽입) 트럭을 내리는(큐에서 삭제) 순서로 코드를 구현했다. 그래서 위의 조건을 생각했지만, 코드의 흐름과 실행되는 순서를 따져보면 7트럭이 이동을 완료하면, 조건을 만족하여 큐에서 삭제하여 큐가 비게 된다. 다음 트럭부터 이동 연산을 해야하는데 큐가 비게 되어 반복문을 종료하게 된다. => 트럭 내리는(큐에서 삭제) 것을 먼저 구현하고, 그 후에 트럭에 올리는(큐에 삽입) 것을 구현하는 순서로 하면 7트럭이 이동을 완료하여 큐에서 삭제하고 큐가 비더라도 바로 다음에서 다음 트럭인 4가 탑승 조건에 검사 후 트럭에 올라고 큐에 삽입된다!

3. 연산을 반복하는 순서, 반복 조건, 종료 조건을 설계하는 것이 많이 약한 듯하다. 큐에 초기 셋팅 : 0번째 트럭 넣어준다. =>다음으로 올라갈 트럭의 인덱스는 idx+1로 증가시켜야하고, time 또한 1 증가한 time+1이 되어야한다. 큐에 0번째 트럭 넣어주고 idx, time을 1씩 증가시키지 않아서 큐에서 삭제할 때 idx를 출력하면 0이 2번 출력됐던 것이였다!

4. 트럭 승/하차 순서 : 처음에만 트럭 승차를 먼저하지만, 이후에 반복할 때에는 트럭을 승차하기 위해서는 다리의 W와 L에 따라 트럭 하차를 먼저 해주고나서야 트럭 승차를 할 수 있다!

두번째로 풀었음에도 불구하고 문제를 맞추지 못했다. 트럭이 다리에서 내려가는 조건은 생각했지만, 올라가는 조건에서 다리 위 트럭들 무게의 "합"으로 올바르지 않았다. 종료 조건을 생각해봤지만 반복 조건을 적절하게 떠올리지 못했다.

두가지 솔루션이 있다. 두 솔루션의 반복 조건은 각각

1. while(!q.isEmpty()) : 큐가 비지 않는 동안 연산을 반복수행하기 때문에 처음에 0번째 트럭을 넣어주어야 하고, 이에 따라 idx와 time은 1 증가해야한다. 큐는 다리를 의미하고, 다리(큐)에 0번째 트럭을 올렸다는 건 1초가 지난 후이기 때문이다. 로직 순서 ① 트럭 하차 ② 트럭 승차 ③ time 증가 : 제일 마지막에 위치

2. while(count<N) : 다리를 지나간 트럭의 갯수 count를 카운팅하여 N개만큼 반복한다! 1번과 다르게 큐가 비는 것과 상관없이 반복해서 연산을 수행하기 때문에 반복문 전에 필수적으로 0번째 트럭을 큐에 넣지 않아도 된다. ① time 증가 ② 트럭 하차 ③ 트럭 승차 이 두번째 솔루션의 로직 흐름과 순서가 더 직관적이였다. int idx = 0, weight = 0, time = 0, count = 0; wilhe(count<N) { t++;

첫번째와 두번째 솔루션의 차이점은 idx=1번째 트럭부터 반복문을 실행 는지와 idx=0번째 트럭부터 반복문을 실행하는지의 차이이고, time이 증가하는 위치가 트럭 승차 후에 있는지 제일 먼저 있는지이다.

첫번째 코드 분석

1. 첫번째 코드는 큐가 비지 않는 동안 반복문을 수행하기 때문에 반복문 시작 전에 큐에 넣어줘야한다. 따라서 반복문 시작 전에 0번째 트럭 을 큐에 넣고, 이로 인해 idx, time을 1씩 증가시킨다. 그리고 난 후 반복문을 수행하는데, 반복문 들어가기 전에 이미 time을 증가했기 때문에 time++;이 나오면 안 되고, 증가된 time에서의 트럭 이동/하차/승차 처리를 해줘야한다! 그리구 난 후에 time이 증가해야한다!!!

2. 1번 분석의 흐름에 따라 time은 하차, 승차 후에 마지막에 1 증가한다. 0번째 트럭을 큐에 넣을 때 승차한 시간인1이 아니라 승차하기 전 0을 넣어주고 0과 w차이 나는지 비교한다. 0번째 트럭이 들어간 시간이 1이 아니라 0인 이유 time++가 하차/승차한 후에 마지막에 증가되기 때문에 첫번째 코드에서 0번째 트럭이 올라간 후의 시간인 1로 해버리면 time은 8인 상태에서 큐가 비어서 정답은 딱 그 시점에서의 time=8이 정답이지만, 바로 적절한 로직 처리로 break문을 해주지 않는 이상, 코드 흐름은 아래를 실행해서 time은 8이 아니라 1이 큰 9가 되버린다! 시간이 제일 마지막에 증가하기 때문에, t=7에서 트럭 하차/승차 후 t=8이 된다!!!!!!!! 이것을 해석해보면, 마지막 트럭이 하차하기 직전의 시간이 우리가 원하는 정답이 된다!!다시 말해, 트럭이 다리에 올라간 후, 내려간 후의 시간이 아니라 올라가기 직전, 내려가기 직전의 시간으로 시간 비교와 반복문을 수행한다!!!

반면 두번째 코드는 반복문에서 0번째 트럭부터 트럭 이동/하차/승차하기 때문에 반복문 처음부터 바로 time++이 나와서 time이 증가하는 것이 맞는 것이다!

세번째로 풀었는데 틀린 이유 - 두번째 풀이법(다리 통과한 트럭 갯수 이용)

반복문 시작전에 변수, 객체들 초기화, 생성만 해주고, 반복문 내에서 0번째 트럭부터 연산수행하는 것이 로직 핵심이다. 그런데 반복문 시작전에 큐에 0번째 트럭을 넣어버렸다. 이 말은, 다리 위에 트럭이 올라갔다는 것이고, 그러면 time과 idx는 1이 증가해야한다. 하지만 반복문 구조는 0번째 트럭부터 반복을 시작하는 것으로 짜여져있기 때문에 틀린 로직이 되버리고, 오답이 되는 것이다!