https://school.programmers.co.kr/learn/courses/30/lessons/17680
프로그래머스
코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.
programmers.co.kr
Level 2. [1차] 캐시
2018 KAKAO BLIND RECRUITMENT
접근 방식
큐를 사용한다.
1. 초반(캐시 공간이 남을 때)에는 queue에 도시를 추가한다.
-> 이때 캐시에 이미 존재하는 도시를 추가할 차례라면, 해당 도시는 삭제하고 queue의 마지막에 새로 추가한다.
2. 캐시 공간이 남지 않았을 때에는 queue에 존재하는지 안 하는지 확인한다.
-> 존재한다면, hit이며 queue에서 해당 도시를 삭제하고 queue의 마지막에 새로 추가한다.
-> 존재하지 않는다면, miss이며 queue의 맨 처음 도시를 삭제하고, 맨 마지막에 새로 도시를 추가한다.
처음 코드
import java.util.*;
class Solution {
public int solution(int cacheSize, String[] cities) {
int answer = 0;
if(cacheSize==0)
return 5*cities.length;
Queue<String> queue = new LinkedList<>();
for(int i=0; i<cities.length; i++) {
//초반 (캐시 공간이 남음)
if(queue.size()<cacheSize) {
// 존재하면 그냥 넘어간다 -> hit
if(queue.contains(city)) {
//// 수정한 부분 ////
answer++;
}
//안 존재하면 miss, 추가해준다
else {
queue.add(city);
answer+=5;
}
}
//확인 필요
else {
//갖고 있는 애면 hit고, queue에 순서 바꿔줌
if(queue.contains(city)) {
queue.remove(city);
queue.add(city);
answer++;
}
//안 갖고 있는 애면 miss
else {
queue.remove();
queue.add(city);
answer+=5;
}
}
}
return answer;
}
}
처음 코드는, 모든 도시를 소문자와 대문자를 구분하여 오답이었다. 해당 문제는 반복문을 시작하기 전, 소문자로 모두 변경하여 해결하였다.
두 번째 문제는, 수정한 부분이라고 표시된 부분이 잘못되었었는데 캐시의 공간이 남았고, 이미 존재하는 도시를 확인할 때가 문제였다. 이미 존재하고 캐시의 공간이 남았다면 그냥 넘어가는 방법으로 문제를 풀었었는데, 해당 경우는 큐의 순서를 바꾸어주어야 한다는 사실을 간과하였다. 해당 도시를 삭제하고, 다시 큐에 추가하는 방법으로 해결할 수 있었다.
최종 코드
import java.util.*;
class Solution {
public int solution(int cacheSize, String[] cities) {
int answer = 0;
if(cacheSize==0)
return 5*cities.length;
Queue<String> queue = new LinkedList<>();
for(int i=0; i<cities.length; i++) {
String city = cities[i].toLowerCase();
//초반 (캐시 공간이 남음)
if(queue.size()<cacheSize) {
// 존재하면 그냥 넘어간다 -> hit
if(queue.contains(city)) {
queue.remove(city);
queue.add(city);
answer++;
}
//안 존재하면 miss, 추가해준다
else {
queue.add(city);
answer+=5;
}
}
//확인 필요
else {
//갖고 있는 애면 hit고, queue에 순서 바꿔줌
if(queue.contains(city)) {
queue.remove(city);
queue.add(city);
answer++;
}
//안 갖고 있는 애면 miss
else {
queue.remove();
queue.add(city);
answer+=5;
}
}
}
return answer;
}
}
고찰
해당 문제는 LRU에 대한 정확한 이해와 응용이 필요한 문제이다. LRU에 대한 이론이 정확하지 않다면 제대로 풀 수 없다.
또, queue를 사용하면 단순하게 풀 수 있다.
여러 가지 테스트 케이스를 계속해서 확인해보면서 정답을 맞출 수 있는 문제였다.
많은 테스트 케이스가 있는 경우에는 문제를 정확하게 이해할 수 있는데, 그렇지 못하다면 쉽지 않을 것 같았다.
많은 경우의 수를 스스로도 생각해볼 수 있어야 할 것 같다.
또, 학기 중에 LRU 알고리즘을 작성해본 적 있는데, 그때보다 훨씬 수월하게 풀 수 있었기 때문에 그래도 조금은 성장한 것(...) 같다고 느꼈다.
많이 풀어보고 해결할 수 있는 능력을 길러야겠다.
'알고리즘 > Java' 카테고리의 다른 글
[프로그래머스] Java - n^2 배열 자르기 (0) | 2023.05.05 |
---|---|
[프로그래머스] Java - 행렬의 곱셈 (0) | 2023.05.05 |
[프로그래머스] Java - 괄호 회전하기 (0) | 2023.05.03 |
[프로그래머스] Java - H Index (0) | 2023.05.02 |
[프로그래머스] Java - 멀리 뛰기 (0) | 2023.05.02 |