프로그래머스 - [1차]캐시(C++)

문제 출처: https://programmers.co.kr/learn/courses/30/lessons/17680

문제 난이도

Lv 2

문제 접근법

삽입 정렬을 사용했다.

LRU 캐시 알고리즘 이라던가 cachehit, cachemiss의 개념을 찾는데 더 걸렸던 문제다. 처음엔 vector로 무작정 구현했는데 삽입 정렬을 사용하는게 바로 알고리즘 측면에서 맞다고 생각한다.

통과 코드

#include <string>
#include <vector>

using namespace std;


int solution(int cacheSize, vector<string> cities) {
	int answer = 0;
	vector<string> lru(cacheSize);
    
    for (int i = 0; i < cities.size(); i++) {
		for (int j = 0; j < cities[i].size(); j++) {
			if (cities[i][j] >= 'A' && cities[i][j] <= 'Z') {
				cities[i][j] = tolower(cities[i][j]);
			}
		}
	}
    
	for (int i = 0; i < cities.size(); i++) {
		int pos = -1;
		for (int j = 0; j < cacheSize; j++) {
			if (lru[j] == cities[i]) pos = j;
		}
		if (pos == -1) { //cachemiss
			for (int j = cacheSize - 1; j >=1; j--) lru[j] = lru[j - 1];
			answer += 5;
		}
		else { //cachehit
			for (int j = pos; j >=1; j--) lru[j] = lru[j - 1];
			answer += 1;
		}
        if(!lru.empty()) lru[0] = cities[i]; //cacheSize 0 일때 오류 방지
	}
	return answer;
}