캐시(난이도: 하) 알고리즘 문제
하편
4. 도시 객체 배열을 처리할 수 있는 객체를 생성합니다.
입력 형식 1 : 캐시 크기(cacheSize)와 도시이름 배열(cities)을 입력받는다.
입력 형식 3 : cities는 도시 이름으로 이뤄진 문자열 배열로, 최대 도시 수는 100,000개이다.
조건 1 : 캐시 교체 알고리즘은 LRU(Least Recently Used)를 사용한다.
도시이름을 객체로 만든것처럼, 도시이름 배열을 일급 컬랙션 객체로 만들어 처리합니다.
배열로 한다면... 너무 번거로운 작업이 많아져 List로 처리하였습니다.
@Test
public void 도시_포함() {
Cities cities = new Cities(getStringArr("Jeju", "Pangyo"));
assertThat(true, is(cities.contains(new City("Jeju"))));
}
@Test
public void 도시_삭제() {
Cities cities = new Cities(getStringArr("Jeju"))
.addFirst(new City("aaa"))
.remove(new City("aaa"));
assertThat(false, is(cities.contains(new City("aaa"))));
}
@Test
public void 도시_앞쪽으로_추가() {
Cities cities = new Cities(getStringArr("Jeju"))
.addFirst(new City("aaa"));
cities.remove(cities.size()-1);
assertThat(true, is(cities.contains(new City("aaa"))));
}
package kakao.cache;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.stream.Collectors;
import java.util.stream.Stream;
public class Cities {
private static final int MAX_LENGTH = 100001;
private List<City> cities;
public Cities() {
cities = new ArrayList<>();
}
public Cities(String... cities) {
if (cities == null) throw new IllegalArgumentException();
make(Arrays.asList(cities).stream()
.map(City::new)
.collect(Collectors.toList()));
}
public Cities(List<City> cities) {
if (cities == null) throw new IllegalArgumentException();
make(cities);
}
private void make(List<City> cities) {
if (cities.size() > MAX_LENGTH) throw new IllegalArgumentException();
this.cities = new ArrayList<>();
this.cities.addAll(cities);
}
public boolean contains(City city) {
return cities.stream().anyMatch(_city -> _city.equals(city));
}
public Cities addFirst(City city) {
cities.add(0, city);
return new Cities(cities);
}
public Cities remove(City city) {
cities.remove(city);
return new Cities(cities);
}
public Cities remove(int index) {
cities.remove(index);
return new Cities(cities);
}
public int size() {
return cities.size();
}
public Stream<City> stream() {
return cities.stream();
}
}
addFirst() : 캐시 교체 알고리즘은 LRU(Least Recently Used)를 충족하기 위해 사용했습니다.
가장 최근에 사용된 것이 front(0번 인덱스)에 위치하고, 최근이 아닐 수록 rear로 index가 밀리게 됩니다.
remove() : 체이닝이 되도록 다시 객체를 반환합니다.
[테스트 하기 편하기 위해서 체이닝 했을뿐, 반드시 객체를 반환할 필요는 없습니다.]
객체에 사용된 count를 넣는 방식도 있지만 불필요한 인스턴스 필드를 생성하여 관리 이슈가 생기는 것을 피하기 위해 index를 기준으로 하였습니다.
5. 캐시 크기 객체 만들기
입력 형식 1 : 캐시 크기(cacheSize)와 도시이름 배열(cities)을 입력받는다.
입력 형식 2 : cacheSize는 정수이며, 범위는 0 ≦ cacheSize ≦ 30 이다.
다른 값이 들어올 수 없도록 객체로 만들면 관리 이슈가 줄어들게 됩니다.
@Test
public void cacheSize_0_일때() {
new CacheSize(0);
}
package kakao.cache;
public class CacheSize {
private static final int MAX_SIZE = 31;
private Integer size;
public CacheSize(Integer size) {
if (size < 0 || size > MAX_SIZE) throw new IllegalArgumentException();
this.size = size;
}
public int toInt() {
return size;
}
public boolean same(int number) {
return size == number;
}
}
해설에 보면 공개된 대부분의 LRU 구현 코드는 0일 때 비정상적인 작동을 한다는군요.
생성자에 넣어서 생성된다면, 입력 형식 2의 범위를 커버할 수 있습니다.
6.캐시 객체 생성
지금까지 만든 것들을 조합하면, 캐시 객체가 완성 됩니다.
@Test
public void LRU_cacheSize_0_작동() {
Cache first = new Cache(0)
.executeLRU(new City("first"));
assertThat(false, is(first.contains(new City("first"))));
}
@Test
public void LRU_cacheSize_작동() {
Cache hasSecond = new Cache(1)
.executeLRU(new City("first"))
.executeLRU(new City("second"));
assertThat(false, is(hasSecond.contains(new City("first"))));
assertThat(true, is(hasSecond.contains(new City("second"))));
}
package kakao.cache;
public class Cache {
private CacheSize cacheSize;
private Cities cities;
public Cache(CacheSize cacheSize, Cities cities) {
this.cacheSize = cacheSize;
this.cities = cities;
}
public Cache(Integer cacheSize) {
this.cacheSize = new CacheSize(cacheSize);
cities = new Cities();
}
public Cache executeLRU(City city) {
if (cacheSize.same(0)) return new Cache(cacheSize.toInt());
if (contains(city)) {
remove(city);
}
if (isFull()) {
remove(lastIndex());
}
return addFirst(city);
}
public boolean contains(City city) {
return cities.contains(city);
}
private boolean isFull() {
return cities.size() >= cacheSize.toInt();
}
private int lastIndex() {
return cities.size()-1;
}
private Cache addFirst(City city) {
return new Cache(cacheSize, cities.addFirst(city));
}
private Cache remove(City city) {
return new Cache(cacheSize, cities.remove(city));
}
private Cache remove(int index) {
return new Cache(cacheSize, cities.remove(index));
}
}
LRU는 가장 최근에 사용된 것이 캐시에 남아 있어야 함으로, 사이즈가 1일 경우 가장 최근에 사용한 것만 갖고 있도록 하였습니다.
executeLRU() :
1. 캐시 사이즈가 0인 예외적인 상황이 아니라면 객체를 front에 추가 합니다.
2. 해당 값을 갖고 있다면, 추가 전 삭제합니다.
3. 캐시에 없는 값이 들어왔다면, rear(오랫동안 사용하지 않은 객체)를 삭제합니다.
lastIndex() : 가독성을 위해, 한 줄 짜리 매쏘드를 궃이 사용했습니다.
(-1과 같은 숫자가 들어오는걸 피하고 싶었습니다.)
캐시는 완성이 되었습니다.
7. 실행 객체 생성
OOP인 만큼 실행 또한 객체로 대체합니다.
@Test
public void 결과_확인() {
assertThat(50, is(new CityCache(3)
.executeTime(
getStringArr("Jeju", "Pangyo", "Seoul", "NewYork", "LA", "Jeju", "Pangyo", "Seoul", "NewYork", "LA")
)));
assertThat(21, is(new CityCache(3)
.executeTime(
getStringArr("Jeju", "Pangyo", "Seoul", "Jeju", "Pangyo", "Seoul", "Jeju", "Pangyo", "Seoul")
)));
assertThat(60, is(new CityCache(2)
.executeTime(
getStringArr("Jeju", "Pangyo", "Seoul", "NewYork", "LA", "SanFrancisco", "Seoul", "Rome","Paris", "Jeju", "NewYork", "Rome")
)));
assertThat(52, is(new CityCache(5)
.executeTime(
getStringArr("Jeju", "Pangyo", "Seoul", "NewYork", "LA", "SanFrancisco", "Seoul", "Rome","Paris", "Jeju", "NewYork", "Rome")
)));
assertThat(16, is(new CityCache(2)
.executeTime(
getStringArr("Jeju", "Pangyo", "NewYork", "newyork")
)));
assertThat(25, is(new CityCache(0)
.executeTime(
getStringArr("Jeju", "Pangyo", "Seoul", "NewYork", "LA")
)));
}
package kakao.cache;
public class CityCache {
private Cache cache;
private ExecuteResult executeResult;
public CityCache(Integer cacheSize) {
cache = new Cache(cacheSize);
executeResult = new ExecuteResult();
}
public int executeTime(String... cities) {
new Cities(cities).stream().forEachOrdered(this::execute);
return executeResult.sum();
}
private void execute(City city) {
executeResult.increase(cache.contains(city));
cache.executeLRU(city);
}
}
executeTime() : forEachOrdered로 진행되어야만 LRU가 되겠죠?
execute() : this::excute로 표현하기위해 매쏘드로 뺐습니다.
주저리 주저리...
네이밍이 너무나 어렵네요...
Cache에 LRU알고리즘이 있어야하는데, 정작 사용하는 콜렉션은 Cities를 사용하고 있으니..
CitiCache가 적합할 것 같고... 여러가지 고민을 하던중 외부에서 사용할 때, Cache보단 CityCache가 하위처럼 보이기 때문에 CityCache로 하였습니다.
원래는 Cache가 Abstract class로 있고, CityCache와 CityCacheVO로 구현하면 확장하기 좋지만 일급 콜렉션에 대한 공부가 부족하다는 것을 느끼며 구현에 실패하게 되었습니다.
LRU도 객체로 빼야하나 고민도 하다가 알고리즘인 만큼 매쏘드로 하였습니다.
'프로그래밍 > 알고리즘' 카테고리의 다른 글
| 캐시(난이도: 하) [상편] (0) | 2018.02.22 |
|---|---|
| 다트 게임(난이도: 하) [하편] (0) | 2018.02.14 |
| 다트 게임(난이도: 하) [상편] (0) | 2018.02.14 |
| 비밀 지도(난이도: 하) JAVA (0) | 2018.02.14 |
kakao_dart.zip