📜 문제
- 아래 조건을 충족하는 자료 구조 만들기
- 동일한 key에 서로 다른 타임 스탬프(시간인듯)를 갖는 다중 value 저장
- 그리고 특정 타임 스탬프(시간)에 대한 key 값 검색
주어진 TimeMap 클래스의 생성자, set(), get() 함수를 조건에 맞게 작성하는 문제이다.
조건만 보고는 이해하기 힘들기에 예제에서 친절히 설명해줬다.
- 하나의 key에는 bar, bar2 처럼 여러 값이 저장될 수 있다.
- 검색 시에는
[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로 지정한다.
- 매개변수로 들어온
value와timestamp로 valueSet 생성. - map에 key가 존재하는지 확인 (존재하지 않으면 valueList 초기화)
- valueList에 valueSet 삽입.
- 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가 오름차순으로 정렬 돼 있음. (문제 조건 중 제시)
-
timestamp와 동일한 time을 가진 value가 존재하면 해당 value 반환.
-
timestamp보다 작은 경우
- 현재 result가 가진 time 값보다 큰 경우 result에 해당 value 저장.
- 그렇지 않은 경우
start = half + 1로 더 큰 값 탐색
-
timestamp 보다 큰 경우:
end = half-1하여 작은 값 탐색 -
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();
}
}
✨ 결과
