[프로그래머스] [1차] 캐시

https://programmers.co.kr/learn/courses/30/lessons/17680?language=python3 

코딩테스트 연습 - [1차] 캐시

---

[풀이 방법]

1. 연결리스트 자료구조를 갖는 cache선언

     -> cache에는 참조한 순서대로 city가 저장된다. (가장 최근에 참조한 city는 맨 뒤에 존재!)

 

2. 다음과 같은 과정을 cities배열에 돌며 반복한다.

    2-1) cache에 현재 city의 값이 존재 하는 경우

           ->  실행시간 1 증가

           ->  cache에서 가장 최근에 참조한 city는 cache의 마지막 위치에 존재해야 함

                 따라서 cache에서 참조한 city를 제거하고 다시 마지막 위치에 추가

    2-2) cache에 현재 city의 값이 존재 하지 않는 경우

            -> 실행시간 5 증가

            -> cache에 city 추가

            -> cache의 크기가 허용된 크기보다 크다면 cache의 맨 앞에 존재하는 city를 삭제

 

3. 실행시간 반환

 

*추가적인 설명*

- city는 공백, 특수문자가 없는 문자열로 대소문자를 구분하지 않는다. 따라서 저장하거나 city의 값이 있는지 확인 할 경우 대문자를 기준으로 수행한다.

- 연결리스트 자료구조를 사용한 이유?

   참조된 도시의 시간을 갱신할 때 중간에 존재하는 값을 삭제해야 하는데, 이렇게 배열에서 중간에 있는 값을 삭제할 경우에는 이어져있는 주소의 값만 변경해주는 연결리스트를 사용하면 효율성이 좋다:)

 

[코드_Java]

import java.util.LinkedList;

class Solution {
    public int solution(int cacheSize, String[] cities) {
        int answer = 0;
        LinkedList<String> cache = new LinkedList<>();
        for(String city: cities) {
            if(cache.contains(city.toUpperCase())){
                answer++;
                cache.remove(cache.indexOf(city.toUpperCase()));
                cache.add(city.toUpperCase());
            } else {
                answer += 5;
                cache.add(city.toUpperCase());
                if(cache.size() > cacheSize) cache.remove();
            }
        }
        
        return answer;
    }
}