[17680] 캐시

✔ 캐시

[프로그래머스 17680]

문제 분석하기

큐를 이용해 큐를 캐시크기만큼 유지

만약 큐 안에 도시이름이 있을 경우 도시를 다시 꺼내 큐에 저장하고 실행시간은 1 증가

만약 큐 안에 도시이름이 없을 경우 가장 앞의 도시를 제거하고, 새로운 도시를 저장한 후 실행시간은 5 증가

손으로 풀어보기

1. 도시이름을 대문자로 변환
2. 캐시가 0보다 작다면 모두 cache miss이므로 실행시간이 5씩 증가
3. 만약 큐 안에도시이름이 있을 경우 도시를 다시 꺼내 큐에 저장하고 실행시간은 1 증가
4. 만약 큐 안에 도시이름이 없을 경우 새로운 도시를 저장한 후 실행시간은 5 증가
   • 이때 캐시가 크기를 초과하면 가장 앞의 도시를 제거
5. 실행시간을 반환

슈도코드 작성하기

cacheSize(캐시크기)
cities(도시이름)
answer(실행시간)
queue(도시이름을 저장할 큐)
for(city -> cities만큼) {
    upperCity(city를 대문자로 변환한 문자)
    if(cacheSize가 0이라면) {
        모두 캐시를 사용하지 못하므로 answer += 5;
    }
    else if(queue에 upperCity가 존재한다면) {
        queue에서 꺼내 다시 queue에 저장
        answer += 1;
    }
    else {
        if(queue의 크기가 cachedSize보다 크거나 같다면)
            queue의 가장 앞의 도시 꺼내기
        queue에 upperCity 저장
        answer += 5;
    }
}
answer 반환

코드 구현하기

/**
 * 17680) 캐시
 */
public class L030_17680 {
    // cacheSize(캐시크기)
    // cities(도시이름)
    public int solution(int cacheSize, String[] cities) {
        // answer(실행시간)
        int answer = 0;
        // queue(도시이름을 저장할 큐)
        Queue<String> queue = new LinkedList<>();
        for (String city : cities) {
            // upperCity(city를 대문자로 변환한 문자)
            String upperCity = city.toUpperCase();
            // cacheSize가 0이라면 (cache miss)
            if (cacheSize == 0) {
                // 모두 캐시를 사용하지 못하므로 answer += 5;
                answer += 5;
            }
            // queue에 upperCity가 존재한다면 (cache hit)
            else if (queue.contains(upperCity)) {
                // queue에서 꺼내 다시 queue에 저장
                Iterator<String> iterator = queue.iterator();
                while (iterator.hasNext()) {
                    String element = iterator.next();
                    if (element.equals(upperCity)) {
                        iterator.remove();
                        break;
                    }
                }
                queue.offer(upperCity);
                // answer += 1;
                answer += 1;
            }
            // queue에 upperCity가 존재하지 않는다면 (cache miss)
            else {
                // queue의 크기가 cachedSize와 같다면
                if (queue.size() == cacheSize)
                    // queue의 가장 앞의 도시 꺼내기
                    queue.poll();
                // queue에 upperCity 저장
                queue.offer(upperCity);
                // answer += 5;
                answer += 5;
            }
        }
        // answer 반환
        return answer;
    }

    // 테스트 케이스
    public static void main(String[] args) {
        L030_17680 solution = new L030_17680();

        int cacheSize = 0;
        String[] cities = { "LA", "LA" };

        int result = solution.solution(cacheSize, cities);

        System.out.println(result);
    }
}