Daily LeetCode Challenge - 981. Time Based Key-Value Store

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

오늘 문제는 문제의 요구조건에 부합하는 TimeMap() 클래스를 만드는 문제였다.
문제에서 요구한 조건은 timestamp 값과 함께 key, value 를 넣고, key 값과 timestamp 값으로 value 를 가져올때, 해당 timestamp 값과 같거나 작은 timestamp 값과 일치하는 value 값을 가져오는 문제였다.
TreeMap 에 있는 메서드인 floorEntry() 를 쓰면 금방 해결할 수 있지만, 연습도 할겸 직접 만들어서 풀어보기로 했다.

class TimeMap() {

    val map = HashMap<Pair<String, Int>, String>()
    
    fun set(key: String, value: String, timestamp: Int) {
        val pair = Pair(key, timestamp)
        map.put(pair, value)
    }

    fun get(key: String, timestamp: Int): String {
        val pair = Pair(key, timestamp)
        if(map.containsKey(pair)) {
            return map.get(pair)!!
        }
        else {
            val prevPair = findPrevKey(key, timestamp)
            return map.get(prevPair) ?: ""
        }
    }
    
    private fun findPrevKey(key : String, timestamp : Int) : Pair<String, Int> {
        var time = timestamp
        while(time != 0){
            if(map.containsKey(Pair(key, time))) return Pair(key, time)
            time--
        }
        return Pair("", 0)
    }
}

Pair 를 사용하여 key 와 timestamp 를 묶고 value 값을 따로 넣어주었다.
역시 메서드를 안쓰니까 구현이 약간 지저분해지고 길어졌다.
다음은 메서드를 써서 푼 풀이이다.

class TimeMap() {
    private val map = hashMapOf<String, TreeMap<Int, String>>()
   
    fun set(key: String, value: String, timestamp: Int) {
        map.putIfAbsent(key,  TreeMap())
        map[key]?.set(timestamp, value)
    }

    fun get(key: String, timestamp: Int): String {
      return  map[key]?.floorEntry(timestamp)?.value?:""
    }

}

Pair 를 사용했던 부분을 TreeMap 으로 바꾸어서 floorEntry 를 써서 검색할때 시간을 줄이려고 하였다. 아래 풀이의 총 시간복잡도는 log(n) 이 된다. 위에서 floorEntry 메서드를 쓰지 않고 풀때도 Pair 대신 TreeMap 을 썼으면 더 좋았을거 같다.

매번 알고리즘 문제를 풀때마다 느끼는 사실이지만, 다른 사람의 풀이를 보고 배우는 점이 굉장히 많은것 같다. 이래서 지식의 공유가 중요한가보다.