leetcode time based key value store

https://leetcode.com/problems/time-based-key-value-store

class TimeMap {

    private Map<String, List<Pair<String, Integer>>> map;

    public TimeMap() {
        map = new HashMap<>();
    }
    
    public void set(String key, String value, int timestamp) {
        if(!map.containsKey(key)) map.put(key, new ArrayList<>());
        map.get(key).add(new Pair(value, timestamp));
    }
    
    public String get(String key, int timestamp) {

        if(!map.containsKey(key)) return "";
        List<Pair<String, Integer>> list = map.get(key);
        int left = 0;
        int right = list.size() - 1;
        String res = ""; 
        while(left < right) {
            // right 을 mid - 1 로 해주기 위해서는 mid 를 반올림 한 인덱스로 만들어줘야 루프를 탈출할 수 있다. 
            int mid = left + (right - left + 1) / 2; 
            if(list.get(mid).getValue() <= timestamp) {
                left = mid; // 이 if 조건을 만족하는 가장 큰 left 가 계속해서 갱신된다.
                            // 왜? if 조건을 만족할 때 마다 left 가 점점 mid 쪽으로 이동해서 커지기 떄문임 
            }
            else {
                right = mid - 1;
            }
        }

        return list.get(left).getValue() <= timestamp ? list.get(left).getKey() : "";
    }

}

 

left = mid + 1; right = mid; 패턴으로도 풀 수 있다. 단, res 를 계속 업데이트 해줘야 한다. 

class TimeMap {

    private Map<String, List<Pair<String, Integer>>> map;

    public TimeMap() {
        map = new HashMap<>();
    }
    
    public void set(String key, String value, int timestamp) {
        if(!map.containsKey(key)) map.put(key, new ArrayList<>());
        map.get(key).add(new Pair(value, timestamp));
    }
    
    public String get(String key, int timestamp) {

        if(!map.containsKey(key)) return "";
        List<Pair<String, Integer>> list = map.get(key);
        int left = 0;
        int right = list.size() - 1;
        String res = ""; 
        while(left < right) {
            int mid = left + (right - left) / 2; 
            if(list.get(mid).getValue() <= timestamp) {
                res = list.get(mid).getKey();
                 // 우선 mid 가 조건을 만족하는 가장 큰 timestamp 를 가진 값이 된다. 
                 // 왜 res 를 계속 업데이트 해주는가 ? -> 마지막에 left = mid + 1 에 의해 while 루프를 탈출한 left가 timestamp 보다 클 수 도 있기 때문임 
                left = mid + 1;
            }
            else {
                right = mid;
            }
        }

        // 마지막으로 나온 left 가 mid + 1 인데, 이것역시 timestamp 보다 작다면 left 가 가장 큰 값이 될 것이고, 
        // 아니면 그대로 res 를 리턴해주자. 
        return list.get(left).getValue() <= timestamp ? list.get(left).getKey() : res;
    }
}