[프로그래머스] 캐시 (JAVA/자바) - 2018 카카오 기출
문제
프로그래머스>코딩테스트 연습>2018 KAKAO BLIND RECRUITMENT>[1차] 캐시 - https://programmers.co.kr/learn/courses/30/lessons/17680
풀이
LRU
방식으로 캐시 크기에 따른 실행시간을 측정하는 문제이다.
LRU
방식 : 가장 오랫동안 참조되지 않은 페이지를 교체하는 기법- cache hit : 실행시간
+1
- cache miss : 실행시간
+5
-
city이름의 대소문자는 구분하지 않는다
라는 조건이 있으므로, 모든 문자를 소문자로 변경한다. -
우선 캐시에 해당 city 문자열이 들어있는지 확인한다.
2-1.캐시에 존재하면(cache hit)
, 실행 시간을 +1 한다. 이후 해당 index의 access time만 업데이트 해준다.
2-2.캐시에 존재하지 않으면(cache miss)
, 실행 시간을 +5 한다.- 캐시에 빈 공간이 있으면 그냥 데이터를 넣는다. (+access time도 기록한다)
- 캐시에 빈 공간이 없으면 access time이 가장 오래된 위치의 index를 찾아 해당 데이터를 변경한다. (+access time도 변경한다.)
-
단, 캐시의 크기가 0이라면 캐시에 아무 데이터도 저장해둘 수 없으므로 무조건 cache miss가 일어나기 때문에 예외처리 해주면 된다.
코드
class Solution {
public static int solution(int cacheSize, String[] cities) {
// 대소문자 구분이 없으므로 모두 소문자로 변경
for (int i = 0; i < cities.length; i++) {
cities[i] = cities[i].toLowerCase();
}
String[] cache = new String[cacheSize]; // 캐시
int[] cache_access_time = new int[cacheSize]; // 캐시에 들어있는 값이 참조된 time
// initialize
for (int i = 0; i < cacheSize; i++) {
cache[i] = "";
}
int time = 0;
if(cacheSize==0){ // 캐시 용량이 0이면 예외처리
return 5 * cities.length;
}
int cnt = 0; // 캐시 안에 들어있는 데이터의 수
for (int i = 0; i < cities.length; i++) {
String now = cities[i];
boolean cached = false;
// 캐시에 now가 존재하는지 확인
for (int j = 0; j < cacheSize; j++) {
if (cache[j].equals(now)) { // cache hit
time ++;
cache_access_time[j] = time;
cached = true;
break;
}
}
if(!cached){ // cache miss
time += 5;
if(cnt < cacheSize){ // 캐시 안에 남은 공간이 있으면 넣는다.
cache[cnt] = now;
cache_access_time[cnt++] = time;
}else{ // 남은 공간이 없다면 가장 오랫동안 참조되지 않은 위치(=참조 시간이 가장 작은 위치)를 찾아 변경한다
int min_idx = 0;
int min = time;
for (int j = 0; j < cacheSize; j++) {
if(min > cache_access_time[j]){
min = cache_access_time[j];
min_idx = j;
}
}
cache[min_idx] = now;
cache_access_time[min_idx] = time;
}
}
}
return time;
}
}
정리
난이도 : LEVEL 2
🤦♀️ 메모
- 크게 어렵다기 보다는 문제의 조건을 잘 읽고 적용해야 했던 문제이다. 대소문자의 구분이 없다는 조건이나, hit/miss에 따라 실행 시간이 어떻게 더해지는지, 캐시 안에 있는 데이터 중에 가장 오래 참조되지 않은 인덱스가 무엇인지 코드로 잘 풀어내야 했다!
참고 사이트
딱히 없음
Author And Source
이 문제에 관하여([프로그래머스] 캐시 (JAVA/자바) - 2018 카카오 기출), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@yanghl98/프로그래머스-캐시-JAVA자바-2018-카카오-기출저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)