[LeetCode, java] - Snapshot Array

특정 배열의 인덱스별로 스냅샷을 생성하는 클래스를 구현하는 문제이다.

TreeMap이라는 자료구조가 생소했는데 이번에 floorEntry() 메서드로 새로 학습했다.

floorEntry는 같거나 가장 큰 key=value 엔트리를 반환한다.

문제 풀면서 snap()의 구현이 너무 심플해서 충격받았음;;

        snapshot.put(snapId, val); // snap()에서만 할 것이라고 생각했던 action이 set()에서 하네

난 snap()에서 for문을 돌려가면서 put하는 것이라고 생각했는데
그랬더니 바로 시간 초과나더라고...

그래도 이진 탐색 분류치고 로직은 덜 어렵다.

import java.util.ArrayList;
import java.util.List;
import java.util.Map;
import java.util.TreeMap;

public class SnapshotArray2 {

    private int snapId;

    private List<TreeMap<Integer, Integer>> snapshots;

    public SnapshotArray2(int length) {
        snapId = 0;
        snapshots = new ArrayList<>(); // 초기화

        for(int i = 0; i < length; i++) {
            TreeMap<Integer, Integer> map = new TreeMap<>();
            map.put(0,0);
            snapshots.add(map);
        }
    }
    public void set(int index, int val) {
        TreeMap<Integer, Integer> snapshot = snapshots.get(index);
        snapshot.put(snapId, val);
    }

    public int snap() {
        return snapId++; // 이게 가장 충격임... 걍 ++이 끝이라구요..?
    }

    public int get(int index, int snap_id) {
        TreeMap<Integer, Integer> snapshot = snapshots.get(index);
        Map.Entry<Integer, Integer> entry = snapshot.floorEntry(snap_id);
        return entry.getValue();
    }
}