캐시(난이도: 하) [상편]

캐시(난이도: 하) 알고리즘 문제

---

상편

---

요구 사항

입력 형식

  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. 실행 시간의 시간 객체 생성

표현으로는 시간이지만, 테스트에서 제시한 시간은 초,분,시 가 아닌 단순한 숫자입니다.

조건 2 : cache hit일 경우 실행시간은 1이다.
조건 3 : cache miss일 경우 실행시간은 5이다.

1.1. Number interface 생성.

공통적으로 실행시간의 증가와 결과 값을 가져오는 기능이 필요합니다.

package kakao.cache;

public interface Number {
    public <T> T increase();
    public int toInt();
}

1.2. 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씩 증가하게 됩니다.

1.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씩 증가하게 됩니다.

2. 출력 객체 생성 (방금 만든 객체를 조합합니다.)

출력 형식 : 입력된 도시이름 배열을 순서대로 처리할 때, “총 실행시간”을 출력한다.

@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개 이상의 값의 더하기 연산을 암시합니다. [유지보수할 사람을 위해...]

3. 도시 객체 만들기 ("도시이름"을 도시라는 객체로 관리합니다.)

입력 형식 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").equals(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시 필수)

하편에서 이어집니다...