[Leetcode] 1396. Design Underground System

Implement the class UndergroundSystem that supports three methods:

1. checkIn(int id, string stationName, int t)

• A customer with id card equal to id, gets in the station stationName at time t.
• A customer can only be checked into one place at a time.

2. checkOut(int id, string stationName, int t)

• A customer with id card equal to id, gets out from the station stationName at time t.

3. getAverageTime(string startStation, string endStation)

• Returns the average time to travel between the startStation and the endStation.
• The average time is computed from all the previous traveling from startStation to endStation that happened directly.
• Call to getAverageTime is always valid.

You can assume all calls to checkIn and checkOut methods are consistent. That is, if a customer gets in at time t1 at some station, then it gets out at time t2 with t2 > t1. All events happen in chronological order.

Example 1:

Input
["UndergroundSystem","checkIn","checkIn","checkIn","checkOut","checkOut","checkOut","getAverageTime","getAverageTime","checkIn","getAverageTime","checkOut","getAverageTime"]
[[],[45,"Leyton",3],[32,"Paradise",8],[27,"Leyton",10],[45,"Waterloo",15],[27,"Waterloo",20],[32,"Cambridge",22],["Paradise","Cambridge"],["Leyton","Waterloo"],[10,"Leyton",24],["Leyton","Waterloo"],[10,"Waterloo",38],["Leyton","Waterloo"]]

Output
[null,null,null,null,null,null,null,14.00000,11.00000,null,11.00000,null,12.00000]

Explanation
UndergroundSystem undergroundSystem = new UndergroundSystem();
undergroundSystem.checkIn(45, "Leyton", 3);
undergroundSystem.checkIn(32, "Paradise", 8);
undergroundSystem.checkIn(27, "Leyton", 10);
undergroundSystem.checkOut(45, "Waterloo", 15);
undergroundSystem.checkOut(27, "Waterloo", 20);
undergroundSystem.checkOut(32, "Cambridge", 22);
undergroundSystem.getAverageTime("Paradise", "Cambridge");       // return 14.00000. There was only one travel from "Paradise" (at time 8) to "Cambridge" (at time 22)
undergroundSystem.getAverageTime("Leyton", "Waterloo");          // return 11.00000. There were two travels from "Leyton" to "Waterloo", a customer with id=45 from time=3 to time=15 and a customer with id=27 from time=10 to time=20. So the average time is ( (15-3) + (20-10) ) / 2 = 11.00000
undergroundSystem.checkIn(10, "Leyton", 24);
undergroundSystem.getAverageTime("Leyton", "Waterloo");          // return 11.00000
undergroundSystem.checkOut(10, "Waterloo", 38);
undergroundSystem.getAverageTime("Leyton", "Waterloo");          // return 12.00000

Example 2:

Input
["UndergroundSystem","checkIn","checkOut","getAverageTime","checkIn","checkOut","getAverageTime","checkIn","checkOut","getAverageTime"]
[[],[10,"Leyton",3],[10,"Paradise",8],["Leyton","Paradise"],[5,"Leyton",10],[5,"Paradise",16],["Leyton","Paradise"],[2,"Leyton",21],[2,"Paradise",30],["Leyton","Paradise"]]

Output
[null,null,null,5.00000,null,null,5.50000,null,null,6.66667]

Explanation
UndergroundSystem undergroundSystem = new UndergroundSystem();
undergroundSystem.checkIn(10, "Leyton", 3);
undergroundSystem.checkOut(10, "Paradise", 8);
undergroundSystem.getAverageTime("Leyton", "Paradise"); // return 5.00000
undergroundSystem.checkIn(5, "Leyton", 10);
undergroundSystem.checkOut(5, "Paradise", 16);
undergroundSystem.getAverageTime("Leyton", "Paradise"); // return 5.50000
undergroundSystem.checkIn(2, "Leyton", 21);
undergroundSystem.checkOut(2, "Paradise", 30);
undergroundSystem.getAverageTime("Leyton", "Paradise"); // return 6.66667

Constraints:

• There will be at most 20000 operations.
• 1 <= id, t <= 10^6
• All strings consist of uppercase, lowercase English letters and digits.
• 1 <= stationName.length <= 10
• Answers within 10^-5 of the actual value will be accepted as correct.

각 고객들은 Underground System 을 딱 한번만 들어왔다가 빠져나갈 수 있다. 즉, checkIn → checkOut 과정은 한번만 일어난다. 이것은 곧 checkOut 수행시에 checkOut 작업을 기록할 필요는 없다는 것을 의미한다.

checkOut 은 이전에 기록된 작업을 꺼내서 연산하는 역할이 되어야 한다.

아래의 코드는 두개의 map 을 가진다. checkIn 의 시점을 기록하는 map 과 averageTime 을 계산하는맵이다.

checkout 시점에 checkIn 시에 기록해두었던 map 에서 시작 station 과 time 값을 가져와서 연산을 해서 averageTimeMap 에 차곡차곡 쌓아둔다.

averageTimeMap 은 여태까지 from → to station 의 모든 시간의 합과 고객의 수를 가지고 있으므로, 최종 단계에서는 이 값을 꺼내서 나눠주기만 하면 된다.

package leetcode;

import java.util.HashMap;
import java.util.Map;

public class UndergroundSystem {

    Map<Integer, Pair> checkInMap;
    Map<String, Counter> averageTimeMap;

    public UndergroundSystem() {
        this.checkInMap = new HashMap<>();
        this.averageTimeMap = new HashMap<>();
    }

    public void checkIn(int id, String stationName, int t) {
        checkInMap.put(id, new Pair(stationName, t));
    }

    public void checkOut(int id, String stationName, int t) {
        Pair pair = checkInMap.get(id);
        String fromTo = pair.stationName + "_" + stationName;

        Counter counter = averageTimeMap.getOrDefault(fromTo, new Counter());

        counter.sum += t - pair.t;
        counter.traveler++;

        averageTimeMap.put(fromTo,  counter);
    }

    public double getAverageTime(String startStation, String endStation) {
        Counter counter = averageTimeMap.get(startStation + "_" + endStation);

        return (double)counter.sum / (double)counter.traveler;
    }

    static class Counter {
        int sum;
        int traveler;
    }

    static class Pair {
        String stationName;
        int t;

        public Pair(String stationName, int t) {
            this.stationName = stationName;
            this.t = t;
        }
    }
}