981. Time Based Key-Value Store java 풀이

이거는 굉장히 쉽다.

 

timestamp 는 무조건 증가하니까(이분탐색)

들고와서(HashMap)

이하를 return 해주면 된다.

 

class Store {
    int timestamp;
    String value;
}

class TimeMap {
    // key - value 와 timestamp 를 저장한다.
    // get이 핵심
        // get 할 때 key 와 timestamp 를 쓰면, 그 timestamp 이하의 key 에 대한 value 가 return 된다.

    // 풀이 방법

    // get
        // key 로 찾으면 timestamp 를 찾는다.
        // 저장을 순서대로 한다면?
        // 결국 key 가져와서 거기서 이분탐색으로 timestamp 구하고, 해당하는 value 구하면 된다.

    // set
        // 이건 쉽다. 그냥 저장해주면 된다.

    Map<String, List<Store>> map;

    public TimeMap() {
        map = new HashMap<>();
    }
    
    public void set(String key, String value, int timestamp) {
        // 이분탐색을 위한 세팅
        // 시간은 선형으로 무조건 증가한다.

        // key 에 대해 이분탐색을 진행할 Store 객체를 만든다. 대상은 timestamp
        // 나머지는 하나씩 넣어주면 된다.
        List<Store> arr = map.getOrDefault(key, new ArrayList<Store>());
        Store store = new Store();
        store.value = value;
        store.timestamp = timestamp;
        arr.add(store);
        map.put(key, arr);
    }
    
    public String get(String key, int timestamp) {
        // key 로 찾아와서
            // 이분탐색을 진행한 뒤에
                // 거기서 현재보다 작거나 같은 값의 value 를 돌려주면 된다.
        List<Store> arr = map.get(key);

        // 비었으면 "" 돌려줌
        if(arr == null) return "";

        // 가장 큰 값의 timestamp 를 최종 크기로 하고 이분탐색 시작
        int right = arr.size() - 1;
        int left = 0;
        int mid;
        int storeTimestamp;

        String answer = "";

        Store ans = null;
        while(left <= right) {
            // 가운데 값을 구하고, 그것의 timestamp 를 들고온다.
            mid = (left + right) / 2;
            ans = arr.get(mid);
            storeTimestamp = ans.timestamp;

            // 가져온 값이 더 작으면
            if(storeTimestamp <= timestamp) {
                answer = ans.value;  // 일단 이하니까 이건 충족시킨다.
                left = mid + 1; // 그리고 더 큰 값을 찾아본다.
            } else if(storeTimestamp > timestamp) {
                // 가져온 값이 더 크면
                // 더 작은 쪽을 찾으면 된다.
                right = mid - 1;
            }
        }

        return answer;
    }
}

/**
 * Your TimeMap object will be instantiated and called as such:
 * TimeMap obj = new TimeMap();
 * obj.set(key,value,timestamp);
 * String param_2 = obj.get(key,timestamp);
 */