[Algorithm] 프로그래머스 Lv2 다리를 지나는 트럭

안녕하세요 rosepurple입니다. :)

오늘 푼 알고리즘 문제 풀이를 작성해보도록 하겠습니다!

문제

오늘은 아래 문제를 풀어봤습니다. (약 40분 소요)

programmers.co.kr/learn/courses/30/lessons/42583

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

풀이

문제를 풀기 위해서 해당 인덱스 트럭이 지나가고 있는 위치, 다리 위에 있는 트럭들의 인덱스, 다리가 버틸 수 있는 남은 무게를 체크했습니다.

int answer = 1;
int truckIndex = 0;
int remainWeight = weight;
int[] truckLocationArray = new int[truck_weights.length];
ArrayList<Integer> currentBridgeTruck = new ArrayList<>();

remainWeight = 남은 무게, truckLocationArray = 트럭이 지나가고 있는 위치, currentBridgeTruck = 다리 위에 있는 트럭들의 인덱스입니다.

다리 위에 올라갈 첫 번째 트럭의 인덱스입니다. (2번까지 다리 위에 있으면, 3번을 가리킵니다.)

그리고 answer가 왜 1인지 궁금하실 텐데요. 트럭이 다리 위에서 모두 통과해야(나와야)하므로 마지막에 트럭이 온전하게 나올 수 있게 1로 초기화했습니다.

저는 위치를 체크하기 때문에 딱 트럭 길이만큼 왔을 때 answer을 반환하면 트럭이 아예 통과하지 않은 상태여서 1씩 작게 리턴되더라고요.

 

while (truckLocationArray[truck_weights.length - 1] > -1) {
    answer++;
	...
}

while문을 순회하는 조건은 마지막 트럭의 위치가 -1보다 클 때까지입니다.

트럭 위치가 bridge_length와 같으면 -1로 초기화해주기 때문에 위와 같이 조건을 달아주었습니다.

 

if (truckIndex < truck_weights.length && truck_weights[truckIndex] <= remainWeight) {
    currentBridgeTruck.add(truckIndex);
    remainWeight -= truck_weights[truckIndex];
    truckIndex++;
}

 

 

다음 트럭을 가리키는  truckIndex가 트럭 배열 길이를 넘지 않고, 다음 인덱스의 트럭 무게가 남은 무게보다 적으면 다리를 건너고 있는 트럭에 추가해주고 남은 무게에서 방금 추가해준 인덱스의 트럭 무게를 빼줍니다.

 

for (int index: currentBridgeTruck) {
    truckLocationArray[index]++;
}

현재 다리를 지나고 있는 트럭의 위치를 1 앞으로 조정해줍니다.

 

for (int i = 0; i < truckLocationArray.length; i++) {
    if (truckLocationArray[i] == bridge_length) {
        truckLocationArray[i] = -1;
        currentBridgeTruck.remove(0);
        remainWeight += truck_weights[i];
    }
    else if (truckLocationArray[i] >= 0){
        break;
    }
}

트럭들의 위치가 다리 길이와 같다면 -1로 초기화시킨 후에 현재 다리에 위치한 트럭 맨 앞을 제거해줍니다.

남은 무게는 통과한 트럭의 무게를 더해줍니다.

 

전체 코드

class Solution {
    public int solution(int bridge_length, int weight, int[] truck_weights) {
        int answer = 1;
        int truckIndex = 0;
        int remainWeight = weight;
        int[] truckLocationArray = new int[truck_weights.length];
        ArrayList<Integer> currentBridgeTruck = new ArrayList<>();

        while (truckLocationArray[truck_weights.length - 1] > -1) {
            answer++;

            if (truckIndex < truck_weights.length && truck_weights[truckIndex] <= remainWeight) {
                currentBridgeTruck.add(truckIndex);
                remainWeight -= truck_weights[truckIndex];
                truckIndex++;
            }

            for (int index: currentBridgeTruck) {
                truckLocationArray[index]++;
            }

            for (int i = 0; i < truckLocationArray.length; i++) {
                if (truckLocationArray[i] == bridge_length) {
                    truckLocationArray[i] = -1;
                    currentBridgeTruck.remove(0);
                    remainWeight += truck_weights[i];
                }
                else if (truckLocationArray[i] >= 0){
                    break;
                }
            }
        }

        return answer;
    }
}

마무리

이번에 제가 정처기 필기시험을 봐서 2주일 가까이 알고리즘을 못 풀었는데요ㅠㅠ

2021년 상반기에 계획 중인 자격증이 몇 개 생겨서 매일은 못 풀겠지만 최대한 풀어서 포스팅해보겠습니다!!

 

이번 포스팅도 읽어주셔서 감사합니다. :)