[알고리즘] LeetCode 981. Time Based Key-Value Store JS

개요

객체형식으로 푸는 문제로 set,get을 정의하는 문제였다.

set은 [key, value, timestamp]형식으로 주어지고 get은 [key, timestamp]형식으로 주어진다. set은 자료구조를 생각해서 데이터를 저장해야하고, get은 키와 일치하거나 가장 가까운 timestamp를 갖는 value를 출력하는게 문제이다.

Time Based Key-Value Store - LeetCode

 

풀이

문제를 처음 읽었을 때 바로 해쉬맵을 셍각하였고 구현했고 get도 단순하게 반복문을 사용해서 구현했다.

 

당연히 시간초과가 떴고 이분탐색으로 구현해야하는 것을 깨닫고 금방 구현을 하긴했다. 항상 이분탐색을 구현하면서 일치하는 숫자를 찾는건 어느정도 해봐서 금방 구현할 수 있었는데 일치하는 숫자가 없을 때는 어떻게 구현을 해야하는지 전혀 감을 잡지못했다. 아래 문제처럼 가장 가까운 timestamp를 찾는 부분에서 mid 값을 리턴해야하는지 mid - 1값을 리턴해야하는지부터 mid - 1값이 0으로 빠지는 등 간단한 구현에서 많이 헤멨다. 다른 사람의 코드를 참고해서 구현을 하긴했는데 이런 것도 왜 자꾸 놓칠까 하면서 현타가 오긴했다. 

 

그리고 놓친 부분에서 시간초과가 또 발생했는데 set해서 value와 timestamp 객체로 저장할 때 (...) spread 연산자를 사용하는 바람에 깊은 복사로 발생한 문제였다. 이런 부분도 잘 신경써야겠다 

/*
 * @lc app=leetcode id=981 lang=javascript
 *
 * [981] Time Based Key-Value Store
 */

// @lc code=start

var TimeMap = function () {
  this.timeMap = new Map();
};

/**
 * @param {string} key
 * @param {string} value
 * @param {number} timestamp
 * @return {void}
 */
TimeMap.prototype.set = function (key, value, timestamp) {
  if (this.timeMap.has(key)) {
    const arr = this.timeMap.get(key);
    arr.push({ value, timestamp });
    this.timeMap.set(key, arr);
  } else this.timeMap.set(key, [{ value, timestamp }]);
  return null;
};

/**
 * @param {string} key
 * @param {number} timestamp
 * @return {string}
 */
TimeMap.prototype.get = function (key, timestamp) {
  const timestamps = this.timeMap.get(key);
  if (!this.timeMap.has(key) || timestamps[0].timestamp > timestamp) return "";
  const len = timestamps.length;

  let lt = 0;
  let rt = len - 1;
  let mid = 0;

  while (lt <= rt) {
    mid = Math.floor((rt + lt) / 2);
    if (timestamps[mid].timestamp === timestamp) return timestamps[mid].value;
    else if (timestamps[mid].timestamp > timestamp) rt = mid - 1;
    else lt = mid + 1;
  }
  if (timestamps[mid].timestamp > timestamp) return timestamps[mid - 1].value;
  return timestamps[mid].value;
};

/**
 * Your TimeMap object will be instantiated and called as such:
 * var obj = new TimeMap()
 * obj.set(key,value,timestamp)
 * var param_2 = obj.get(key,timestamp)
 */
// @lc code=end

 

회고

꽤 오래 붙잡고 있던 문제였는데, 회고해보면 쉬운문제라고 생각해서 혼자 붙잡고있다가 발생한 문제같다. 앞으로는 시간을 지키고 다른 사람의 코드도 잘 읽는 습관을 들이면 더 효율적으로 공부할 수 있을거라고 생각했다.