<java> 프로그래머스 다리를 지나는 트럭 - 자료 구조 Deque

99클럽 코테 스터디 3일차 TIL + 자료 구조 Deque

 

https://school.programmers.co.kr/learn/courses/30/lessons/42583

프로그래머스

 

완전 처음에는 아예 문제를 잘못 읽고 차량이 두대씩 지나가는데 최선의 조건을 구하라는 문제인줄 알고
정렬 후 이진탐색을 쓰려고 하였다.(문제좀 제대로 읽자)
그러나 다시 읽어보니 순서대로 지나가는 문제 임을 알게되었다.

 

문제를 제대로 파악한 후 처음에는

시작 지점과 끝 지점의 index를 저장 해두고 끝 지점의 index가 다리 길이와 같아지면
다음 트럭의 위치를 끝에 갱신해 주는 방식으로 진행하려고 하였다.

그러나 그렇게 하려면 시작과 끝 만이 아니라 중간 index 모두를 알고 있어야 했기에 start, end를 가지고 있는 방식은 불가능 하다는 것을 알게되었다.

두번째는 list를 사용해 다리 전체를 표현하고 다리 하나하나에 들어갈때 마다 넣은 다음
시간이 지나면 for 문을 돌면서 하나씩 옮겨주는 방식에 대해 고민했는데

다른 것 보다 시간 복잡도가 너무 클것 같았고 더 좋은 방식이 있을 것 같았다.

그러다 마지막으로 떠올린 것이 무빙워크 처럼 다리에 올라간 차가 움직이는 것이 아닌
다리자체가 움직이는 것으로
제일 뒤의 다리가 사라지고 제일 앞의 다리를 추가 해주는 방식으로 하는 것이 좋겠다라는 결론을 내렸다.
앞과 뒤를 모두 동시에 접근 해야한다는 것을 깨닫고 바로 Deque를 써야 한다고 생각하고
정답을 구현해 나갔다.

 

중간 오류

1. 내린 트럭의 값을 total에서 빼는 것을 잊음

2. 마지막 트럭이 올라가고 내릴 때 까지의 시간이 있는데 시간을 더해 주지 않음

문제를 제대로 읽자 제발!!
주석 처리 해서 과정을 먼저 설계하고 문제 풀이를 시작하자

import java.util.*;
import java.io.*;

class Solution {
    public int solution(int bridge_length, int weight, int[] truck_weights) {
        int time = 0;
        int total = 0;
        
        Deque<Integer> deq = new LinkedList<>();
        //아무것도 없는 다리는 -1로 가득 채우기
        for(int i = 0; i< bridge_length; i++){
            deq.add(-1);
        }
        
        // total + truck[i] <= weight -> 두번째 차 진입
        int i = 0;
        while(i < truck_weights.length){
            if(deq.peekLast() != -1){
                total -= truck_weights[deq.peekLast()];
            }
            if(total + truck_weights[i] <= weight){
                deq.addFirst(i);
                total += truck_weights[i];
                i++;
            }else{
               deq.addFirst(-1);
            }
            deq.pollLast();
            time++;
            // System.out.println(deq);
        }

        return time + bridge_length;
    }
}