카카오 신입 공채 1차 코딩 테스트에 있는 알고리즘 문제를 풀어봅니다.
캐시(난이도: 하) 알고리즘 문제
입력 형식
1. 캐시 크기(cacheSize)와 도시이름 배열(cities)을 입력받는다.
2. cacheSize는 정수이며, 범위는 0 ≦ cacheSize ≦ 30 이다.
3. cities는 도시 이름으로 이뤄진 문자열 배열로, 최대 도시 수는 100,000개이다.
4. 각 도시 이름은 공백, 숫자, 특수문자 등이 없는 영문자로 구성되며, 대소문자 구분을 하지 않는다. 도시 이름은 최대 20자로 이루어져 있다.
출력 형식
1. 입력된 도시이름 배열을 순서대로 처리할 때, “총 실행시간”을 출력한다.
조건
1. 캐시 교체 알고리즘은 LRU(Least Recently Used)를 사용한다.
2. cache hit일 경우 실행시간은 1이다.
3. cache miss일 경우 실행시간은 5이다.
1. 도시 객체 만들기 ("도시이름"을 도시라는 객체로 관리합니다.)
입력 형식 4 : 각 도시 이름은 공백, 숫자, 특수문자 등이 없는 영문자로 구성되며, 대소문자 구분을 하지 않는다. 도시 이름은 최대 20자로 이루어져 있다.
@Test (expected = IllegalArgumentException.class)
public void 도시명_글자만() {
new City(" s d d ");
}
@Test
public void 도시_만들기() {
new City("seoul");
}
@Test
public void 도시_이름_비교() {
assertThat(true, is(new City("seoul").same(new City("Seoul"))));
}
package kakao.cache;
public class City {
private static final int MAX_LENGTH = 21;
private String city;
public City(String city) {
if (city == null || city.isEmpty() || city.length() > MAX_LENGTH) throw new IllegalArgumentException();
if (!city.matches("^[a-zA-Z]*$")) throw new IllegalArgumentException();
this.city = city.trim().toLowerCase();
}
@Override
public String toString() {
return city;
}
@Override
public boolean equals(Object o) {
if (this == o) return true;
if (o == null || getClass() != o.getClass()) return false;
return this.city.toString().equals(o.toString());
}
}"공백, 숫자, 특수문자 등이 없는 영문자"의 조건을 충족하기 위해
생성자에 있는 "^[a-zA-Z]*$"가 제일 중요하죠.
그리고 "대소문자 구분을 하지 않는다"는 조건을 충족하기 위해 city를 만들고 toLowerCase()를 사용합니다.
equals() : 객체를 비교하는 것이 아닌 객체의 String값을 비교합니다. (list에서 remove시 필수)
2. 도시 객체 배열을 처리할 수 있는 객체를 생성합니다.
입력 형식 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를 기준으로 하였습니다.
3. 캐시 크기 객체 만들기
입력 형식 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의 범위를 커버할 수 있습니다.
4.캐시 객체 생성
지금까지 만든 것들을 조합하면, 캐시 객체가 완성 됩니다.
@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과 같은 숫자가 들어오는걸 피하고 싶었습니다.)
캐시는 완성이 되었습니다.
이젠 출력 형식을 만족해야 합니다.
(입력된 도시이름 배열을 순서대로 처리할 때, “총 실행시간”을 출력한다.)
5. 실행 시간의 시간 객체 생성
표현으로는 시간이지만, 테스트에서 제시한 시간은 초,분,시 가 아닌 단순한 숫자입니다.
조건 2 : cache hit일 경우 실행시간은 1이다.
조건 3 : cache miss일 경우 실행시간은 5이다.
공통 적으로 실행시간의 증가와 결과 값을 가져오는 기능이 필요합니다.
package kakao.cache;
public interface Number {
public <T> T increase();
public int toInt();
}5.1. cache hit 객체 생성
package kakao.cache;
public class Hit implements Number {
private Integer count;
public Hit(Integer count) {
this.count = count;
}
@Override
public Hit increase() {
return new Hit(++count);
}
@Override
public int toInt() {
return count;
}
}숫자는 1씩 증가하게 됩니다.
5.2. cache miss 객체 생성
package kakao.cache;
public class Miss implements Number {
private Integer count;
public Miss(Integer count) {
this.count = count;
}
@Override
public Miss increase() {
return new Miss(count + 5);
}
@Override
public int toInt() {
return count;
}
}숫자는 5씩 증가하게 됩니다.
이제 마지막 단계에 이르렀네요.
출력 형식 : 입력된 도시이름 배열을 순서대로 처리할 때, “총 실행시간”을 출력한다.
6. 출력 객체 생성 (5로 만든 객체를 조합합니다.)
@Test
public void 응답시간_포함_1() {
boolean cacheHit = true;
assertThat(1, is(new ExecuteResult().increase(cacheHit).sum()));
}
@Test
public void 응답시간_미포함_5() {
boolean cacheMiss = false;
assertThat(5, is(new ExecuteResult().increase(cacheMiss).sum()));
}package kakao.cache;
public class ExecuteResult {
private Hit hit;
private Miss miss;
public ExecuteResult() {
this.hit = new Hit(0);
this.miss = new Miss(0);
}
public ExecuteResult(Hit hit, Miss miss) {
this.hit = hit;
this.miss = miss;
}
public ExecuteResult increase(boolean isHit) {
if (isHit) {
hit = hit.increase();
} else {
miss = miss.increase();
}
return new ExecuteResult(hit, miss);
}
public int sum() {
return hit.toInt() + miss.toInt();
}
}sum() : 2개 이상의 값의 더하기 연산을 암시합니다. [유지보수할 사람을 위해...]
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")
)));
}
private String[] getStringArr(String... strings) {
return Arrays.asList(strings).stream().toArray(String[]::new);
}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도 객체로 빼야하나 고민도 하다가 알고리즘인 만큼 매쏘드로 하였습니다.