카카오 신입 공채 1차 코딩 테스트 문제 3. 캐시(난이도: 하)

카카오 블라인드 채용에 출제된 문제가 공개돼 풀어보았다. 한 문제당 하나의 클래스로 만들었으며 테스트 코드까지 한꺼번에 올린다. 실제 채용 시험의 채점이 어떻게 이뤄졌는지 모르지만, 문제에 나와있는 입출력은 모두 만족하는 코드이다. 강의할 때도 늘 말하는 것이지만, 코드에 정답은 없다. 문제를 푸는 하나의 방법이 될 수 있음을 기억하고 참고하라.

문제 3. 캐시(난이도: 하)

문제 설명과 해설은 아래 링크를 참고하라.

http://tech.kakao.com/2017/09/27/kakao-blind-recruitment-round-1/

1, 2번 문제는 기본적인 코딩 경험만 있어도 풀 수 있는 문제인 반면에 3번 문제는 캐시 교체 알고리즘인 LRU를 이해할 수 있어야 해서 조금 어렵게 느껴진다. 문제 해결을 위한 코드 자체는 쉬우나 LRU를 모르면 답을 찾기 불가능하다. 하지만 LRU 자체는 어려운 알고리즘이 아니기 때문에 문제를 푸는 도중에 검색해서 이해하고 구현하는 것도 가능했을 것으로 본다.

import org.junit.Test;
 
import static org.junit.Assert.assertEquals;
 
public class Q3 {
    public static void main(String[] args) {
 
    }
 
    @Test
    public void question3TestCase1() {
        int cacheSize = 3;
        String cities[] = {"Jeju",
                "Pangyo",
                "Seoul",
                "NewYork",
                "LA",
                "Jeju",
                "Pangyo",
                "Seoul",
                "NewYork",
                "LA"};
        int out = 50;
 
        assertEquals(out, question3(cacheSize, cities));
 
    }
 
    @Test
    public void question3TestCase2() {
        int cacheSize = 3;
        String cities[] = {"Jeju",
                "Pangyo",
                "Seoul",
                "Jeju",
                "Pangyo",
                "Seoul",
                "Jeju",
                "Pangyo",
                "Seoul"};
        int out = 21;
 
        assertEquals(out, question3(cacheSize, cities));
    }
 
    @Test
    public void question3TestCase3() {
        int cacheSize = 2;
        String cities[] = {"Jeju",
                "Pangyo",
                "Seoul",
                "NewYork",
                "LA",
                "SanFrancisco",
                "Seoul",
                "Rome",
                "Paris",
                "Jeju",
                "NewYork",
                " Rome"};
        int out = 60;
 
        assertEquals(out, question3(cacheSize, cities));
    }
 
    @Test
    public void question3TestCase4() {
        int cacheSize = 5;
        String cities[] = {"Jeju",
                "Pangyo",
                "Seoul",
                "NewYork",
                "LA",
                "SanFrancisco",
                "Seoul",
                "Rome",
                "Paris",
                "Jeju",
                "NewYork",
                "Rome"};
        int out = 52;
 
        assertEquals(out, question3(cacheSize, cities));
    }
 
    @Test
    public void question3TestCase5() {
        int cacheSize = 2;
        String cities[] = {"Jeju",
                "Pangyo",
                "NewYork",
                "newyork"};
        int out = 16;
 
        assertEquals(out, question3(cacheSize, cities));
    }
 
    @Test
    public void question3TestCase6() {
        int cacheSize = 0;
        String cities[] = {"Jeju",
                "Pangyo",
                "Seoul",
                "NewYork",
                "LA"};
        int out = 25;
 
        assertEquals(out, question3(cacheSize, cities));
    }
 
 
    public static int question3(int cacheSize, String[] cities) {
 
        String cache[] = new String[cacheSize];
        for (int i = 0; i < cacheSize; i++) {
            cache[i] = "";
        }
        int exeTime = 0;
        String tempStr;
        boolean isHit;
 
        if (cacheSize == 0) {
            for (String c : cities) {
                exeTime += 5;
            }
            return exeTime;
        }
 
 
        for (String c : cities) {
            isHit = false;
            for (int i = 0; i < cacheSize; i++) {
                if (cache[i].equalsIgnoreCase(c)) {
                    tempStr = cache[i];
                    for (int j = i; j > 0; j--) {
                        cache[j] = cache[j - 1];
                    }
                    cache[0] = tempStr;
                    isHit = true;
                    break;
                }
            }
 
            if (isHit) {
                exeTime += 1;
            } else {
                exeTime += 5;
 
                for (int i = cacheSize - 1; i > 0; i--) {
                    cache[i] = cache[i - 1];
                }
 
                cache[0] = c;
            }
        }
 
        return exeTime;
    }
}