프로그래머스 - 캐시(성공)

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

프로그래머스

30분 전에 포스팅하고 제가 지금까지 한 코드 다 삭제하고 새롭게 풀었습니다...

놀랍게 30분만에 다 풀었네요 저도 신기합니다ㅋㅋ

아래는 문제 풀이입니다.

처음에는 큐로 풀면 되겠다 싶어서 큐로 시도해보았는데 큐에서는 indexOf라는 함수를 지원 안 해주더라고요.

그래서 구글링 한 결과 LinkedList를 쓰고 remove(0)을 하게 되면 큐랑 똑같은 팝이 된다는 말을 듣고 바로

LinkedList로 선언해서 풀었습니다.

이 문제의 핵심은 LRU라는 캐시의 알고리즘인데 쉽게 말하면 가장 오래전에 쓴 놈을 지우고 캐시에 새로운 메모리를 집어넣겠다. 이런 느낌입니다.

그래서 저는 캐시에 순차적으로 저장을 했습니다. 그러므로 가장 오래전에 사용된 배열은 당연히 배열의 0번 인덱스에 존재하도록 됩니다.

그래서 항상 캐시를 삭제해야 될 경우에는 0번 인덱스만을 삭제할 수 있도록 cache.remove(0)을 사용했습니다.

캐시가 hit한 경우에는 LRU라는 캐시의 알고리즘 때문에 cache의 순서를 바꿔주어야 하므로 hit한 캐시의 index를 반환하도록 indexOf 함수를 사용해서 인덱스 번호를 알아냈습니다.

그리고 cache에서 삭제한 후에 다시 맨 뒤에 가장 낮은 우선순위로 지정하면서 문제를 풀이했습니다.

이상한 점이나 궁금하신 점 있으면 댓글 남겨주세요.

class Solution {
        public int solution(int cacheSize, String[] cities) {
            int answer = 0; int cacheCount = 0; int idx = 0;
            LinkedList<String> cache = new LinkedList<>();

            if(cacheSize == 0)
                return 5 * cities.length;

            for(int i=0; i<cities.length; i++){

                if(cache.contains(cities[i].toUpperCase())){ // cache hit
                    answer += 1;

                    idx = cache.indexOf(cities[i].toUpperCase()); // hit한 cache의 index 반환
                    cache.remove(idx);
                    cache.add(cities[i].toUpperCase());

                } else { // cache miss

                    answer += 5;

                    if(cacheSize == cacheCount){ // cache 꽉 참
                        cache.remove(0);
                        cache.add(cities[i].toUpperCase());

                    } else { // cache 비어 있음
                        cache.add(cities[i].toUpperCase());
                        cacheCount++;
                    }


                }

            }

            return answer;
        }
    }