자바 - 프로그래머스 / [1차]캐시

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

프로그래머스

LV 2

 

구현 방법

 0 ≦ cacheSize ≦ 30

cities는 도시 이름으로 이뤄진 문자열 배열로, 최대 도시 수는 100,000개이다.

 

O(n^2)도 가능하다.  큐를 이용하면 조건에 만족하는 사이즈 내에서 LRU를 만족하며 구현 될거라고 생각했다.

그런데 오류가 떠서 생각해보니까 큐 안에 값이 존재하는 경우, 큐 내에서 위치를 업데이트 시켜 줘야 하는걸 깨닮았다.

그런데 또 오류 떠서 보니까, 대소문자 고려 안한다는 걸 반영 안했다! 

그런데 또 오류 떠서 보니까, cachSize가 0인 경우를 고려 안했다.

그거까지 반영하면 통과된다.

 

코드

큐 내에서 위치 업데이트 안 시켜준 코드

import java.util.Queue;
import java.util.LinkedList;

class Solution {
    public int solution(int cacheSize, String[] cities) {
        int answer = 0;
        
        Queue<String> queue = new LinkedList<>();
        
        for(String s : cities) {
            if(queue.contains(s)) {
                answer += 1;
            } else {
                if (queue.size() <= cacheSize) {
                    queue.add(s);
                } else {
                    queue.poll();
                    queue.add(s);
                }
                answer += 5;
            }
        }
        
        return answer;
    }
}

정답 코드

import java.util.Queue;
import java.util.LinkedList;

class Solution {
    public int solution(int cacheSize, String[] cities) {
        int answer = 0;
        
        Queue<String> queue = new LinkedList<>();
        
        for(String s : cities) {
            s = s.toLowerCase();
            
            if(queue.contains(s)) {
                queue.remove(s);
                queue.add(s);
                answer += 1;
            } else {
                if (cacheSize != 0 && queue.size() < cacheSize) {
                    queue.add(s);
                } else if(cacheSize != 0) {
                    queue.poll();
                    queue.add(s);
                }
                answer += 5;
            } 
        }
        
        return answer;
    }
}

 

느낀 점

문제 풀때, 범위 보면서 구현하고 한번에 꼼꼼히 체크하는 습관이 중요함을 느꼈다.

 

참고 블로그

https://crazykim2.tistory.com/571

[JAVA] Queue의 개념 및 사용법 정리