[LeetCode-자바] N_981 Time Based Key-Value Store

0woy·2024년 7월 23일
0

코딩테스트

목록 보기
28/42

📜 문제

  • 아래 조건을 충족하는 자료 구조 만들기
    - 동일한 key에 서로 다른 타임 스탬프(시간인듯)를 갖는 다중 value 저장
    - 그리고 특정 타임 스탬프(시간)에 대한 key 값 검색

주어진 TimeMap 클래스의 생성자, set(), get() 함수를 조건에 맞게 작성하는 문제이다.

조건만 보고는 이해하기 힘들기에 예제에서 친절히 설명해줬다.

  1. 하나의 key에는 bar, bar2 처럼 여러 값이 저장될 수 있다.
  2. 검색 시에는 [key, timestamp] 형식으로 검색한다.
    해당 key에 여러 value가 저장된 경우, 호출한 timestamp 보다 작은 값들 중 가장 큰 timestamp 값을 가진 value를 가져온다.

접근

클래스 이름에서도 알다시피 Map을 구현하는 문제다. 그런데 다중값과 시간을 곁들인..

시간과 값을 변수로 갖는 클래스(이하 Value)를 만들어서 이 Value를 map의 value로 이용해야겠다고 생각했다.

주어진 timestamp보다 작지만 최대값을 찾는 부분은 이진탐색으로 찾을 수 있다.


✍ 부분 코드 설명

Value 클래스 작성

class Value{
    String value;
    int time;

    public Value(){

    }
    public Value(String value, int time){
        this.value = value;
        this.time = time;
    }

    public String getValue(){
        return value;
    }
    public int getTime(){
        return time;
    }
    public void setValue(String value){
        this.value = value;
    }
    public void setTime(int time){
        this.time=time;
    }
}
  • value: 출력할 값
  • time: timestamp

TimeMap 클래스의 생성자 & set 함수 작성

  class TimeMap {
    Map<String, List<Value>> map;
    
    public TimeMap() {
        map = new HashMap<>();
    }
    
    public void set(String key, String value, int timestamp) {
            Value valueSet = new Value(value,timestamp);
        List<Value> valueList = map.getOrDefault(key,null);

        if(valueList == null){
            valueList = new ArrayList<>();
        }

        valueList.add(valueSet);
        map.put(key, valueList);
    
    }
    
    ...
}
  • map : key, value 값을 저장하는 변수
    다중 값을 가지므로 value의 형식은 List로 지정한다.
  1. 매개변수로 들어온 valuetimestampvalueSet 생성.
  2. map에 key가 존재하는지 확인 (존재하지 않으면 valueList 초기화)
  3. valueList에 valueSet 삽입.
  4. map의 key에 valueList 저장

get & binarySearch 함수

	...
    
public String get(String key, int timestamp) {
        List<Value> result = map.getOrDefault(key, null);
        if(result==null){
            return "";
        }
        return binarySearch(result,timestamp,0,result.size()-1);
    }


public String binarySearch(List<Value> values, int target, int start, int end){
	Value result = new Value("", Integer.MIN_VALUE);

    while(start<=end){
    	int half = (start+end)/2;
        Value curValue =values.get(half);
        int curTime = curValue.getTime();

        if(curTime == target){
        	return curValue.getValue();
		}

        if(curTime<target){
        	if(curTime>result.getTime()){
            	result.setTime(curTime);
                result.setValue(curValue.value);
				}	
			start=half+1;
		}
		
        else{
        	end = half-1;
		}
	}	
    return result.getValue();
}

1. get함수

  • map에 key 값이 존재하지 않는 경우 "" 반환
  • 존재하는 경우, binarySearch 함수 호출

2. binarySeach 함수
values 리스트는 timestamp가 오름차순으로 정렬 돼 있음. (문제 조건 중 제시)

  1. timestamp와 동일한 time을 가진 value가 존재하면 해당 value 반환.

  2. timestamp보다 작은 경우

    • 현재 result가 가진 time 값보다 큰 경우 result에 해당 value 저장.
    • 그렇지 않은 경우 start = half + 1로 더 큰 값 탐색
  3. timestamp 보다 경우: end = half-1 하여 작은 값 탐색

  4. result 값 반환


🍳 전체 소스 코드

import java.util.*;

class Value{
    String value;
    int time;

    public Value(){

    }
    public Value(String value, int time){
        this.value = value;
        this.time = time;
    }

    public String getValue(){
        return value;
    }
    public int getTime(){
        return time;
    }
    public void setValue(String value){
        this.value = value;
    }
    public void setTime(int time){
        this.time=time;
    }
}

class TimeMap {

    Map<String, List<Value>> map;
    public TimeMap() {
        map = new HashMap<>();
    }
    
    public void set(String key, String value, int timestamp) {
            Value valueSet = new Value(value,timestamp);
        List<Value> valueList = map.getOrDefault(key,null);

        if(valueList == null){
            valueList = new ArrayList<>();
        }

        valueList.add(valueSet);
        map.put(key, valueList);
    
    }
    
    public String get(String key, int timestamp) {
        List<Value> result = map.getOrDefault(key, null);
        if(result==null){
            return "";
        }
        return binarySearch(result,timestamp,0,result.size()-1);
    }

     public String binarySearch(List<Value> values, int target, int start, int end){
        Value result = new Value("", Integer.MIN_VALUE);

        while(start<=end){
            int half = (start+end)/2;
            Value curValue =values.get(half);
            int curTime = curValue.getTime();

            if(curTime == target){
                return curValue.getValue();
            }

            if(curTime<target){
                if(curTime>result.getTime()){
                    result.setTime(curTime);
                    result.setValue(curValue.value);
                }
                start=half+1;
            }
            else{
                end = half-1;
            }
        }
        return result.getValue();
    }
}

✨ 결과

0개의 댓글