프로그래머스 캐시(lvl2) 풀어보기

문제링크

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

프로그래머스

 

---

문제 핵심

• 캐시 크기(cacheSize)와 도시이름 배열(cities)을 입력받는다.
• cacheSize는 정수이며, 범위는 0 ≦ cacheSize ≦ 30 이다.
• cities는 도시 이름으로 이뤄진 문자열 배열로, 최대 도시 수는 100,000개이다.
• 각 도시 이름은 공백, 숫자, 특수문자 등이 없는 영문자로 구성되며, 대소문자 구분을 하지 않는다. 도시 이름은 최대 20자로 이루어져 있다.

출력 형식

• 입력된 도시이름 배열을 순서대로 처리할 때, "총 실행시간"을 출력한다.

조건

• 캐시 교체 알고리즘은 LRU(Least Recently Used)를 사용한다.
• cache hit일 경우 실행시간은 1이다.
• cache miss일 경우 실행시간은 5이다.

 

---

문제 풀이법

-캐시사이즈 0인지 확인

도시를 돌리며 캐시가 있는지확인

매 캐시 사이즈확인하며 캐시창고 재정비

---

코드

 public static int solution(int cacheSize, String[] cities) {

        int answer = 0;

        if(cacheSize==0){

            return cities.length*5;

        }

        Map<String, Integer> cashStore = new HashMap<>();

        for (String city : cities) {

            int time = 5;

            city = city.toLowerCase();

            System.out.println("시작 캐시 :" + cashStore);

            if (cashStore.containsKey(city)) {

                System.out.println("캐시있음");

                time = 1;

                cashStore.put(city, 0);

            } else {

                System.out.println("캐시주입 예정: " + city);

                cashStore.put(city, 0);

                if (cashStore.size() > cacheSize) {

                    System.out.println("캐시비워야함");

                    String target = "";

                    int max = -1;

                    for (Map.Entry<String, Integer> entry : cashStore.entrySet()) {

                        String key = entry.getKey();

                        Integer value = entry.getValue();

                        if (key.equals(city)) {

                            continue;

                        }

                        if (max < value) {

                            target = key;

                            max = value;

                        }

                    }

                    System.out.println("삭제예정캐시: " + target);

                    cashStore.remove(target);

                }

            }

            for (Map.Entry<String, Integer> entry : cashStore.entrySet()) {

                String key = entry.getKey();

                Integer value = entry.getValue();

                if (key.equals(city)) {

                    continue;

                }

                cashStore.put(key, value + 1);

            }

            answer += time;

            System.out.println("종료후 캐시 :" + cashStore);

        }

        System.out.println(answer);

        return answer;

    }

 

---

결과

---

gpt 피드백

-LRU를 직접 “나이 숫자”로 관리하지 않아도 된다는 거야.

지금 코드는 매 도시마다 Map 전체를 한 번씩 돌면서 모든 값에 +1 하잖아. 그래서 시간복잡도도 늘고 코드도 길어져.

이 문제는 LinkedHashMap의 access-order를 쓰면 훨씬 깔끔해.

 

 

 

---

배운점 느낀점

-95점에서 gpt 없었으면 반례찾다가 포기했을거다

(1,"Jeju", "Pangyo", "Jeju")

이 반례 문제가 내가 max= 0 으로 기본값이였는데

pangyo가 올때 max가 0 이고 jeju 값도 0이여서 

캐시가 두개 들어가는 현상이 발생한다 

그리고 gpt 가준 링크드 해시맵 아주 끝내준느거같다

캐시 사용때마다 제거했다 넣으면 결국 가장 안쓰이는 캐시가

항상 제일 앞에 있을테니 for문도 필요가 없어지니 아주 좋은 의견이다