[HackerLank] Truck Tour - 문제풀이

Description

특정 경로까지의 거리와 연료가 주어졌을때 한바퀴를 왕복 할 수 있는 시작 위치를 찾아 반환하는 문제입니다.

Solution 1. Greedy

public static int truckTour(List<List<Integer>> petrolpumps) {
    // Write your code here
    int len = petrolpumps.size();
    int sum = 0;
    int result = 0;
    int total = 0;
    for (int i = 0; i < len; i++) {

        sum += petrolpumps.get(i).get(0) - petrolpumps.get(i).get(1);
        if (sum < 0) {
            total += sum;
            sum = 0;
            result = i + 1;
        }
    }
    total += sum;
    return total < 0 ? -1 : result;
}

탐욕알고리즘을 통해 현재 위치에서 다음 거리까지의 소모연료를 제외한 남는 값을 더해나가고-가 되는경우 그 다음위치에서부터 다시 트럭을 출발시킵니다. 모든위치에서 진행했을떄 가능한 시작지점이 있다면 해당 지점을 반환하고 전체 순회 후에 total값이 0보다 작다면 모두 돌 수 있는 지점이 없는 것이므로 -1을 반환해줍니다.

유사한 문제로 LeetCode의 Gas Station 문제가 있습니다.

Reference

Discussion on Truck Tour Challenge

 

Gas Station - LeetCode