[프로그래머스/알고리즘] 캐시

캐시

입출력 예제

cacheSize : 3

cities : [ "Jeju","Pangyo","Seoul","NewYork","LA","Jeju","Pangyo","Seoul","NewYork","LA" ]

return :  50

풀이과정

문제에서의 조건은 LRU입니다. 최근에 사용된 것을 교체시켜야 합니다

일단 cacheSize만큼 공간을 만들기 위해 배열로 만들고 캐쉬의 사용 순서를 알기 위한 배열을 또 만들었습니다.

그다음 cities를 한개씩 풀러오면서 캐시에 내용이 존재하지 않으면 값을 집어넣고 사용 순서는 count라는 숫자로 그냥 1개씩 늘렸습니다.

count가 높을 수록 최근에 사용된 캐시라는 것으로 이용해서 캐시 사이즈가 꽉찼을 경우 count가 가장 큰 것을 바꾸는 방법을 이용해서 값을 구했습니다.

소스코드

#include <string>
#include <vector>
#include <algorithm>
using namespace std;

int solution(int cacheSize, vector<string> cities) {
	int answer = 0;
	int recent = 0;
	int count = 0;
	bool flag = false;
	vector<string> cash(cacheSize);
	vector<int> cash_recent(cacheSize);
	
	if (cacheSize == 0)
		return cities.size() * 5;
	for (int i = 0; i<cities.size(); i++) {
		for(int j=0;j<cities[i].length();j++)
			cities[i][j] = toupper(cities[i][j]);
		recent = 0;
		flag = false;
		if (find(cash.begin(), cash.end(), cities[i]) != cash.end()) {
			for (int j = 0; j<cash.size(); j++) {
				if (cash[j] == cities[i]) {
					cash[j] = cities[i];
					cash_recent[j] = count++;
				}
			}
			answer++;
		}
		else {
			for (int j = 0; j<cash.size(); j++) {
				if (cash[j] == "")
				{
					answer += 5;
					cash[j] = cities[i];
					cash_recent[j] = count++;
					flag = true;
					break;
				}
				else {
					if (cash_recent[recent] >= cash_recent[j]) {
						recent = j;

					}
				}
			}
			if (flag == false) {
				cash[recent] = cities[i];
				cash_recent[recent] = count++;
				answer += 5;
			}
		}
	}
	return answer;
}