[HackerRank] Truck Tour

Problem

---

Suppose there is a circle. There are N petrol pumps on that circle. Petrol pumps are numbered 0 to (N-1) (both inclusive). You have two pieces of information corresponding to each of the petrol pump: (1) the amount of petrol that particular petrol pump will give, and (2) the distance from that petrol pump to the next petrol pump.

Initially, you have a tank of infinite capacity carrying no petrol. You can start the tour at any of the petrol pumps. Calculate the first point from where the truck will be able to complete the circle. Consider that the truck will stop at each of the petrol pumps. The truck will move one kilometer for each litre of the petrol.

Input Format

The first line will contain the value of N.
The next N lines will contain a pair of integers each, i.e. the amount of petrol that petrol pump will give and the distance between that petrol pump and the next petrol pump.

 

Constraints:
1 ≤ N ≤ 10^5

1 ≤ amount of petrol, distance ≤ 10^9

Output Format

An integer which will be the smallest index of the petrol pump from which we can start the tour.

Sample Input

3
1 5
10 3
3 4

Sample Output

1

Explanation

We can start the tour from the second petrol pump.

---

어떤 원형 도로가 있고, 그 위에 N개의 주유소가 있습니다. 각 주유소는 0부터 N−1까지 번호가 붙어 있습니다. 각 주유소마다 다음 두 가지 정보가 주어집니다.

1. 해당 주유소에서 주유할 수 있는 기름의 양
2. 해당 주유소에서 다음 주유소까지의 거리

초기 상태에서 트럭은 무한한 용량의 기름탱크를 가지고 있으나, 기름은 비어 있습니다. 어떤 주유소에서든 출발하여 한 바퀴를 돌아 다시 처음 위치로 돌아올 수 있는 첫 번째 주유소의 번호를 찾아야 합니다. 트럭은 각 주유소에서 반드시 정차하며, 1킬로미터를 이동하는데 1리터의 기름을 소모합니다.

 

입력 형식

1. 첫 번째 줄에는 주유소의 개수 N이 주어집니다.
2. 다음 N줄에는 각 주유소의 정보를 나타내는 두 개의 정수(해당 주유소에서 제공하는 기름의 양과 다음 주유소까지의 거리)가 주어집니다.

제약 조건

• 1 ≤ N ≤ 10^5
• 1 ≤ 기름의 양, 거리 ≤ 10^9

출력 형식

한 바퀴를 돌 수 있는 첫 번째 주유소의 번호를 출력합니다.

 

예제 입력

3 
1 5 
10 3 
3 4

 

예제 출력

 

1

 

설명

두 번째 주유소(번호 1)에서 출발하면 트럭은 전체 원형 경로를 완주할 수 있습니다.

 

반응형

Solution

---

public static int truckTour(List<List<Integer>> petrolpumps) {
    int start = 0;  // 시작 지점
    int totalPetrol = 0;  // 전체 남은 기름량
    int currentPetrol = 0;  // 현재까지의 남은 기름량

    for (int i = 0; i < petrolpumps.size(); i++) {
        int petrol = petrolpumps.get(i).get(0);  // 주유소에서 주유할 수 있는 양
        int distance = petrolpumps.get(i).get(1);  // 다음 주유소까지의 거리

        // 현재 주유소에서 얻는 기름량과 거리의 차이를 누적
        currentPetrol += petrol - distance;
        totalPetrol += petrol - distance;

        // 기름이 부족하면 다음 주유소에서 새로 시작
        if (currentPetrol < 0) {
            start = i + 1;
            currentPetrol = 0;
        }
    }

    // 한 바퀴 돌 수 없는 경우는 없음, totalPetrol이 0 이상이면 가능
    return totalPetrol >= 0 ? start : -1;
}

 

1. 각 주유소에서 트럭이 받을 수 있는 기름의 양과 필요한 거리만큼의 기름 소모량을 계산합니다.
2. 기름이 부족하여 이동할 수 없는 경우 다음 주유소에서 새로 시작합니다.
3. 트럭이 한 바퀴를 돌 수 있는 첫 번째 주유소의 번호를 반환합니다.