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

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

프로그래머스

---

풀이방법

해시맵과 Priority Queue를 사용.

1. 현재 문자열을 받아와서 전부 대문자로 바꿔준다(toUpperCase() 사용)
2. 맵에 들어있는 개수가 캐시 사이즈보다 작은경우 (pq와 맵에 값을 넣는다.)
   1. 이미 맵에 들어있는 값이면 +1
   2. 맵에 없는 값이면 +5
3. 맵에 들어있는 개수가 캐시 사이즈와 같은 경우 (pq와 맵에 값을 넣는다.)
   1. 이미 맵에 들어있는 값이면 +1
   2. 맵에 없는 값이면 +5 , 맵에있는 Key-value 와 pq에서 꺼낸 값이 일치할 때 까지 pq에서 값을 빼주고 같다면 map에서 삭제 해준다.

 

3-2 추가 설명

왜? Key-value와 pq에서 꺼낸 값이 일치할 때 까지 빼주는가

 

1. ["Rome", "Jeju", "Seoul", "LA"], casheSize = 3 이라고 하자.
2. Seoul까지는 Map과 Priority Queue에 값이 잘 들어갈 것이고 LA 차례일 때, Map과 pq에 값을 넣고
3. LA가 Map에 없는 값 이기 때문에 pq에서 값을 꺼내서 Map과 value값 비교 후 같으면 삭제 해 준다.
4. Map에 있는 값이 계속 갱신 되기 때문에 값이 같을 때 삭제 해 주면 순서대로 삭제가 된다!

 

소스코드

import java.util.*;

class Solution {
    public int solution(int cacheSize, String[] cities) {
        if(cacheSize == 0) {
            return 5*cities.length;
        }
        int answer = 0;
        HashMap<String,Integer> map = new HashMap<>();
        PriorityQueue<City> pq = new PriorityQueue<>();
        
        for(int i = 0; i< cities.length; i ++) {
            //현재 문자열
            String cur = cities[i].toUpperCase();
            
            if(map.size() < cacheSize) { //맵에 들어있는 개수가 캐시 사이즈보다 작은 경우 -> map과 pq에 넣기
                if(map.containsKey(cur)) { //이미 들어있는 값이면 +1만해줌
                    answer +=1;
                    map.put(cur,i);
                    pq.offer(new City(cur,i));
                    continue;
                }
                map.put(cur,i);
                pq.offer(new City(cur,i));
                answer += 5;
                continue;
            }
            
            //캐시에 있는지 검사 -> 있으면 answer+1과 pq에 값 넣고 map에 업데이트
            if(map.containsKey(cur)) {
                map.put(cur, i);
                pq.offer(new City(cur,i));
                answer += 1;
                continue;
            }
            
            //없으면 -> map과 pq에 값 업데이트 하고 pq 중에 현재와 값 맞는것까지 빼주고 map에서도 삭제, answer+5
            map.put(cur, i);
            pq.offer(new City(cur,i));
            answer += 5;
            while(true) {
                City now = pq.poll();
                if(map.get(now.city) == now.seq) {
                    map.remove(now.city);
                    break;
                }
            }
            
        }

        return answer;
    }
    static class City implements Comparable<City>{
        String city;
        int seq;
        public City(String city, int seq) {
            this.city = city;
            this.seq = seq;
        }
        @Override
        public int compareTo(City o) { //작은거 -> 큰거 순 정렬
            return Integer.compare(this.seq, o.seq);
        }
    }
}

 

 

결과