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

Min Young Kim·2022년 10월 6일
0

algorithm

목록 보기
3/198

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 을 썼으면 더 좋았을거 같다.

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

profile
길을 찾는 개발자

0개의 댓글

Powered by GraphCDN, the GraphQL CDN