문제 URL
https://school.programmers.co.kr/learn/courses/30/lessons/17680
프로그래머스
코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.
programmers.co.kr
[문제 설명]
이 문제는 캐시 크기와 도시이름 배열이 주어질 때, 캐시를 통해 배열을 순서대로 처리하는데 걸리는 총 실행시간을 출력하는 문제이다.
문제를 읽어봤는데도 무슨 의미인지 파악하지 못해서 구글링을 해보았다. 내용을 알고보면 어렵지 않은 문제였다.
[문제 풀이]
문제에는 가장 오랫동안 참조되지 않은 페이지를 교체하는 기법인 LRU 알고리즘이 사용된다.
대문자를 모두 소문자로 바꾸어 준 뒤, cities의 원소를 캐시 크기의 vector<string>에 넣어준다.
캐시 크기가 0인 경우는 캐시 hit이 불가능하기 때문에 모든 원소를 cache miss 시킨다.
cities의 원소가 cache에 이미 있는 경우 LRU를 위해서 캐시에 존재하는 값을 제거 후 벡터의 맨 뒤에 값을 다시 넣어주고,
cities의 원소가 cache에 존재하지 않는 경우 캐시의 맨 앞에 존재하는 값을 제거 후 벡터의 맨 뒤에 값을 넣어준다. 이때, cache가 비어있다면 맨 앞의 값을 제거하는 과정은 생략한다.
#include <string>
#include <vector>
#include <algorithm>
using namespace std;
int solution(int cacheSize, vector<string> cities) {
int answer = 0;
vector<string> cache;
// 캐시 크기가 0
if(cacheSize == 0){
answer = cities.size()*5;
return answer;
}
for(int i=0; i<cities.size(); i++){
string check = cities[i];
transform(check.begin(), check.end(), check.begin(), ::tolower); // 소문자 변환
auto address = find(cache.begin(), cache.end(), check);
/*
리턴 값이 벡터의 end()인 경우 => 해당 원소가 존재하지 않는 것
리턴 값이 벡터의 end()가 아닌 경우 => 해당 원소 존재하는 것
*/
// 캐시에 있을 경우
if(address != cache.end()){
cache.erase(address);
cache.push_back(check);
answer++;
}
// 캐시에 없을 경우
else{
// 캐시에 빈자리 있을 때
if(cache.size() < cacheSize)
cache.push_back(check);
// 캐시에 빈자리 없을 때
else{
cache.erase(cache.begin()); // 맨 첫 번째 원소 삭제
cache.push_back(check);
}
answer += 5;
}
}
return answer;
}