[프로그래머스] 17680 : 캐시 [JAVA] Lv.2

[프로그래머스] 17680 : 캐시 [JAVA] Lv.2

 

1. 준비

대소문자 구분하지 않으므로, 주어진값을 모두 소문자로 변경한 후 계산해야 한다. 그리고 casheSize가 0인 경우에는 하나도 저장할 수 없으니 cities 크기만큼 * 5 해주면 된다.

 

2. 캐시 입출력

이 문제는 deque 를 사용하면 쉽게 풀 수 있다.

ArrayDeque<String> cache = new ArrayDeque<>();

cache.contains(city) <-- city 포함하고 있는지 여부
cache.remove(city) <-- 맨 앞에 나오는 city 삭제
cache.poll(); <-- 맨 앞에꺼 꺼내기
cache.offer(city); <-- 맨 뒤로 넣기

 

---

프로그래머스

 

문제 풀이 설명 (summary)

• Deque를 활용하여 cities 값을 하나씩 검증하여 추가한다.
  • 같다면, 카운트를 + 1 해준다. 이전의 같은 값을 삭제하고 새로 city값을 추가해준다
  • 같지 않다면, 카운트를 +5 하고 가장 먼저 추가한 값을 삭제하고, city값을 추가해준다. 
  • 만약에 casheSize만큼 채워지지 않았다면 꺼내지 않아도 된다. 
• 위 방식으로 모든 city를 순회하면 문제풀이 끝

 

문제 풀이 접근법

• Deque를 활용 (양방향 큐/스택)

 

풀이 코드 (Code)

import java.util.ArrayDeque;

public class Main {
    public static void main(String[] args) {
        int cacheSize = 3;
        String[] cities = new String[]{"Jeju", "Pangyo", "Seoul", "Jeju", "Pangyo", "Seoul", "Jeju", "Pangyo", "Seoul"};
        System.out.println(solution(cacheSize, cities));
    }

    public static int solution(int cacheSize, String[] cities) {
        int time = 0;

        // 예외케이스
        if (cacheSize == 0) {
            return cities.length * 5;
        }

        ArrayDeque<String> cache = new ArrayDeque<>();
        for (String city : cities) {
            city = city.toLowerCase();
            if (cache.contains(city)) { // cache hit
                cache.remove(city);
                time += 1;
            } else { // cache miss
                if (cache.size() == cacheSize) {
                    cache.poll();
                }
                time += 5;
            }
            cache.offer(city);
        }
        return time;
    }
}

 

문제 링크 (Link)

https://school.programmers.co.kr/learn/courses/30/lessons/17680

프로그래머스