[프로그래머스] 레벨2 다리를 지나는 트럭

https://programmers.co.kr/learn/courses/30/lessons/42583?language=java 

코딩테스트 연습 - 다리를 지나는 트럭

 

이 문제는 스택/큐 카테고리에 있어서 처음에는 Queue랑 ArrayList를 사용할 까 고민도 했었다. 하지만 최악의 경우에도 10000*10000의 경우의 수를 가지는 것을 제한조건에서 확인했기 때문에 단순 O(N²) 시간복잡도도 가능할 거라 생각했고, 속도가 조금 느리긴 했지만 이 방법으로 해결했다.

 

그리고 System.arraycopy 메소드는 처음 사용해봤는데 Arrays.copy보다 이 문제에는 더욱 잘 맞아서 유용했다. 인덱스를 사용해서 배열을 잘랐을 때에도 전체 길이는 동일하되, 지정된 인덱스 범위가 아닐 경우에는 0으로 복사되기 때문에 트럭이 진행했을 때의 빈 공간 배열 값을 0으로 쉽게 설정할 수 있었다.

 

1. 다리를 나타내는 배열(bridge), 복사용 임시배열 설정(temp_bridge)하고, 전체 길이는 최대 길이(bridge_length)로 할당

2. 다리(bridge->arr)에 올라가 있는 트럭의 무게를 구해주는 static 메소드 구현(returnWeight)

   2-1. arr[i]의 값이 0이 아니면 해당 다리 구간에 트럭이 있기 때문에 무게에 +

3. 대기 트럭(truck_weights)에 있는 모든 트럭이 다리를 전부 지나가야하기 때문에 각 인덱스로 트럭(truck_index)을 표현한 후, while문에서 조건 처리

   3-1. 시간이 지나면 다리 구간을 모든 트럭이 하나씩 지나가기 때문에 전체 배열을 1만큼 오른쪽 인덱스로 밀고, 마지막 트럭의 값은 무게에서 빼주기

   3-2. 미리 구해놓은 다리의 트럭 무게(chk[1])를 기준으로 다음 진입할 트럭의 무게가 최대 무게보다 적을 경우, 배열의 첫 번째 인덱스 값을 트럭 무게로 설정하고 아닐 경우에는 0으로 설정

   3-3. 시간(cnt)을 +1 해주고, 임시 다리 배열 temp_bridge를 bridge로 전체 복사

4. 마지막 트럭은 무조건 다리 길이만큼 지나기 때문에 결과 변수 cnt에 다리의 길이를 더한 후 결과 출력 

 

---

문제 및 제한조건

 

---

코드

import java.util.Arrays;

class Solution
{
    public static int returnWeight(int[] arr)
    {
        int sum = 0;
        int[] result = new int[2];
        
        for(int i=0; i<arr.length; i++)
        {
            // 다리에서 트럭이 있는 경우에만 무게 더하기
            if(arr[i]!=0)
            {
                sum += arr[i];
            }
        }
        
        return sum;
    }
    
    public int solution(int bridge_length, int weight, int[] truck_weights)
    {
        // 초기 배열 및 변수설정
        int cnt = 0;
        int[] bridge = new int[bridge_length];
        int[] temp_bridge = new int[bridge_length];
        int truck_index = 0;
        Arrays.fill(bridge, 0);
        Arrays.fill(temp_bridge, 0);

        while(truck_index!=truck_weights.length)
        {
            // 다리에 있는 트럭의 무게를 구한 후 밑의 로직에서 사용
            int sum = returnWeight(bridge);
            
            // 다리 배열 전체를 오른쪽으로 1 진행시키고, 마지막 트럭의 무게 빼주기
            sum -= bridge[bridge.length-1];
            System.arraycopy(bridge, 0, temp_bridge, 1, bridge.length-1);
            
            // 무게 여유가 있으면 새로운 트럭이 다리로 올라오고, 트럭 인덱스 증가
            if(sum+truck_weights[truck_index]<=weight)
            {
                temp_bridge[0] = truck_weights[truck_index];
                truck_index++;
            }
            // 무게 여유가 없으면 0으로 채우기
            else
            {
                temp_bridge[0] = 0;
            }
            
            System.arraycopy(temp_bridge, 0, bridge, 0, bridge.length);       
            cnt++;
        }
        
        return cnt+bridge_length;
    }
}