Ruby

def processing_time(size, cites, cache=['']*size)
  search = ->city { (cache.index(city)? 1 : 5).tap {(cache << city).shift} }
  cites.map(&:upcase).sum(&search) 
end

Test

cases = [[3, %w(Jeju Pangyo Seoul NewYork LA Jeju Pangyo Seoul NewYork LA)],
  [3, %w(Jeju Pangyo Seoul Jeju Pangyo Seoul Jeju Pangyo Seoul)],
  [2, %w(Jeju Pangyo Seoul NewYork LA SanFrancisco Seoul Rome Paris Jeju NewYork Rome)],
  [5, %w(Jeju Pangyo Seoul NewYork LA SanFrancisco Seoul Rome Paris Jeju NewYork Rome)],
  [2, %w(Jeju Pangyo NewYork newyork)],
  [0, %w(Jeju Pangyo Seoul NewYork La)]]
expect( cases.map {|e| processing_time(*e)} ).to eq [50, 21, 60, 52, 16, 25]

def measure(size, cities):
    cache =[''] * size

    time = 0
    for city in cities:
        if city.lower() in cache:
            time += 1
        else:
            time += 5
            cache.append(city.lower())
            cache.pop(0)

    return time


test_size = [3, 3, 2, 5, 2, 0]
test_cities = [['Jeju', 'Pangyo', 'Seoul', 'NewYork', 'LA', 'Jeju', 'Pangyo', 'Seoul', 'NewYork', 'LA'], 
               ['Jeju', 'Pangyo', 'Seoul', 'Jeju', 'Pangyo', 'Seoul', 'Jeju', 'Pangyo', 'Seoul'],
               ['Jeju', 'Pangyo', 'Seoul', 'NewYork', 'LA', 'SanFrancisco', 'Seoul', 'Rome', 'Paris', 'Jeju', 'NewYork', 'Rome'],
               ['Jeju', 'Pangyo', 'Seoul', 'NewYork', 'LA', 'SanFrancisco', 'Seoul', 'Rome', 'Paris', 'Jeju', 'NewYork', 'Rome'],
               ['Jeju', 'Pangyo', 'NewYork', 'newyork'],
               ['Jeju', 'Pangyo', 'Seoul', 'NewYork', 'LA']]
result = [measure(s, c) for s, c in zip(test_size, test_cities)]
print(result)

위 처럼 테스트케이스대로 나오긴 하는데 확실히 맞는진 모르겠네여.
잘못된점 수정할점 지적해주세요!
public class kakao {
    public static void main(String[] args) {

        Scanner sc = new Scanner(System.in);
        System.out.print("캐시크기 : ");
        int cacheSize;
        int runtime=0;
        int cnt=0;
        boolean isFind=false;
        while(true){
            cacheSize = sc.nextInt();
            if(cacheSize<0 && cacheSize > 30){
                System.out.println("캐시크기는 0이상 30이하여야 합니다.");
            }else{
                break;
            }
        }

        int S=0;
        while(true){
            System.out.print("도시이름 배열크기 : ");
            S = sc.nextInt();
            if(S > 100000){
                System.out.println("도시이름 배열은 100000을 넘을 수 없습니다.\r다시입력해 주세요.");
            }else{
                break;
            }
        }


        String[] cities = new String[S];
        System.out.println("배열에 넣을 도시 이름을"+S+"만큼 입력하세요");
        for(int i=0;i<S;i++){
            cities[i] = sc.next();
            if(cities[i].length()>20){
                System.out.println("도시이름은 20자를 넘을수 없습니다.\r다시입력하세요.");
                i--;
            }
        }

        String[] cachelist = new String[cacheSize];
        String[] tmplist = new String[cacheSize];
        List<String> list = new ArrayList<String>();
        int start=1;
        for(int i=0;i<S-cacheSize+1;i++){

            for(int j=i;j<cacheSize+i;j++){
                cachelist[cnt] =cities[j];
                cnt++;
            }
            if(start==1){
                for(int z=0;z<cacheSize;z++){
                    runtime = runtime + 5;
                    tmplist[z] = cachelist[z];
                }

            }else{
                for(int t=0;t<cacheSize;t++){
                    if(cachelist[cacheSize-1].equals(tmplist[t])){
                        isFind = true;
                    }
                }
                 if(isFind==true){
                     runtime = runtime + 1;
                 }else{

                     runtime = runtime + 5;
                 }
                 for(int p=0;p<cacheSize;p++){
                     tmplist[p] = cachelist[p];
                 }
                 isFind=false;
            }

            start=2;
            cnt=0;
            }

        System.out.print("캐시크기:"+cacheSize+"  ");
        for(String tmp : cities){
            System.out.print(tmp+" ");
        }
        System.out.println("실행시간: "+runtime);
    }
}

C++입니다. 테스트케이스 RUN 부분까지 만들어봤습니다. LRU가 뭔지 잘 몰라서 검색해서 만들어봤는데 제가 정확한 개념을 몰라서... 일단 드러난 테스트케이스는 통과되네요. 숨겨진 테스트케이스는 통과할지 모르겠습니다. 특별히 알고리즘을 쓰거나 한 게 없어서 복잡도는 O(NM)입니다.

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

//
// convert to capital letter
// if cach size is 0 -> ret 5 * Num of cities
// for all the cities(#1)
//        if cache is not full
//            if city exist in cache(#2-1 for cache)
//            else 
//        if cache is full
//            if city exist in cache(#2-2 for cache)
//            else(#2-3 for new cache)
// ret ans
//
// O(#1 * #2)
// O(cacheSize * num of cities) -> O(NM) ㅠㅜ


int solution(int cacheSize, vector<string> cities)
{
    if (cacheSize == 0) return cities.size() * 5;

    int ACCESS_TIME = 0, ans = 0;
    bool Exist_in_cache;

    for (string &str : cities)
        for (char &ch : str)
            if ('a' <= ch && ch <= 'z') ch += 'A' - 'a'; // to capital. 공백,숫자,특수문자 없음

    vector<pair<string, int>> cache;

    for (auto &city : cities)
    {
        ACCESS_TIME++;
        Exist_in_cache = false;

        // if cache is not full
        if (cache.size() < cacheSize)
        {
            for (auto &each_cache : cache)
                if (each_cache.first == city) {
                    Exist_in_cache = true; 
                    each_cache.second = ACCESS_TIME; 
                    ans += 1; break;
                }
            if (Exist_in_cache == false) {
                cache.push_back({ city, 0 });
                ans += 5;
            }
        }

        // if cache is full
        else
        {
            int index_to_del;
            int min_Access_T = cache[cacheSize - 1].second;
            int CNT = 0;
            for (int i = cacheSize - 1; i >= 0; --i) // check recent first.. old one latter. 뒤쪽이 Recent,
            {
                if (cache[i].first == city) {
                    Exist_in_cache = true;
                    cache[i].second = ACCESS_TIME;
                    ans += 1; break;
                }
                if (cache[i].second <= min_Access_T) {
                    min_Access_T = cache[i].second;
                    index_to_del = i;
                } // 가장 나중에 호출 된 것을 찾는다.
            }
            if (!Exist_in_cache)
            {
                vector<pair<string, int>> NEWcache(cacheSize);
                for (int i = 0; i < cacheSize; ++i)
                    if (i != index_to_del) { NEWcache[CNT++] = cache[i]; }
                cache = NEWcache;
                cache[cacheSize - 1] = {city,0};
                ans += 5;
            }
        }
    }
    return ans;
}
typedef struct testcase
{
    int n;
    vector<string> cities;
    int expectANS;
};

void TESTCASE()
{
    testcase TC[] = {
        {3,{ "Jeju", "Pangyo", "Seoul", "NewYork", "LA", "Jeju", "Pangyo", "Seoul", "NewYork", "LA" } ,50} ,
        {3,{ "Jeju", "Pangyo", "Seoul", "Jeju", "Pangyo", "Seoul", "Jeju", "Pangyo", "Seoul" },21},
        {2,{ "Jeju", "Pangyo", "Seoul", "NewYork", "LA", "SanFrancisco", "Seoul", "Rome", "Paris", "Jeju", "NewYork", "Rome" } ,60},
        {5,{ "Jeju", "Pangyo", "Seoul", "NewYork", "LA", "SanFrancisco", "Seoul", "Rome", "Paris", "Jeju", "NewYork", "Rome" } ,52},
        {2,{ "Jeju", "Pangyo", "NewYork", "newyork" } ,16},
        {0,{ "Jeju", "Pangyo", "Seoul", "NewYork", "LA" } ,25}
    };
    for (const auto& eachTC : TC)
        if (eachTC.expectANS == solution(eachTC.n, eachTC.cities)) std::cout << "OK!\n";
        else std::cout << "WRONG!!!!!\n";
}
int main()
{
    TESTCASE();
    return 0;
}

import org.junit.Test;
import org.thymeleaf.util.StringUtils;

import static org.hamcrest.core.Is.is;
import static org.junit.Assert.assertThat;

public class LRUCacheTest {

    @Test
    public void cacheTest1() {
        assertThat(countTime(0, new String[]{"Jeju", "Pangyo", "Seoul", "NewYork", "LA", "Jeju", "Pangyo", "Seoul", "NewYork", "LA"}), is(50));
        assertThat(countTime(3, new String[]{"Jeju", "Pangyo", "Seoul", "NewYork", "LA", "Jeju", "Pangyo", "Seoul", "NewYork", "LA"}), is(50));


        assertThat(countTime(3, new String[]{"Jeju", "Pangyo", "Seoul", "Jeju", "Pangyo", "Seoul", "Jeju", "Pangyo", "Seoul"}), is(21));
        assertThat(countTime(2, new String[]{"Jeju", "Pangyo", "Seoul", "NewYork", "LA", "SanFrancisco", "Seoul", "Rome", "Paris", "Jeju", "NewYork", "Rome"}), is(60));
        assertThat(countTime(5, new String[]{"Jeju", "Pangyo", "Seoul", "NewYork", "LA", "SanFrancisco", "Seoul", "Rome", "Paris", "Jeju", "NewYork", "Rome"}), is(52));
        assertThat(countTime(2, new String[]{"Jeju", "Pangyo", "NewYork", "newyork"}), is(16));
        assertThat(countTime(0, new String[]{"Jeju", "Pangyo", "Seoul", "NewYork", "LA"}), is(25));

        assertThat(countTime(0, new String[]{"a"}), is(5));
        assertThat(countTime(0, new String[]{"a", "b"}), is(10));
        assertThat(countTime(0, new String[]{"a", "b", "c"}), is(15));

        assertThat(countTime(1, new String[]{"a"}), is(5));
        assertThat(countTime(1, new String[]{"a", "b"}), is(10));
        assertThat(countTime(1, new String[]{"a", "b", "c"}), is(15));

        assertThat(countTime(3, new String[]{"a"}), is(5));
        assertThat(countTime(3, new String[]{"a", "b"}), is(10));
        assertThat(countTime(3, new String[]{"a", "b", "c"}), is(15));

        assertThat(countTime(30, new String[]{"a"}), is(5));
        assertThat(countTime(30, new String[]{"a", "b"}), is(10));
        assertThat(countTime(30, new String[]{"a", "b", "c"}), is(15));


        assertThat(countTime(1, new String[]{"a"}), is(5));
        assertThat(countTime(1, new String[]{"a", "a"}), is(6));
        assertThat(countTime(1, new String[]{"a", "a", "a"}), is(7));

        assertThat(countTime(3, new String[]{"a", "b", "c", "d", "a", "b", "c"}), is(7*5));

        assertThat(countTime(3, new String[]{"a", "b", "c", "a", "b", "c", "a"}), is(3*5+4));

    }

    private int countTime(int cacheSize, String[] cities) {
        CityCache lruCache = new CityCache(cacheSize);
        return lruCache.getTotalSpendTime(cities);
    }
}

class CityCache {
    private static final int IN_CACHE_TIME = 1;
    private static final int IN_DB_TIME = 5;
    private static final int NOT_IN_CACHE = -1;
    private int cacheSize;
    private String[] cache;


    public CityCache(int cacheSize) {
        if(cacheSize < 0 || cacheSize > 30) throw new IllegalArgumentException("캐시 사이즈는 0~30 사이어야 합니다. ");

        this.cacheSize = cacheSize;
        this.cache = new String[cacheSize];
    }

    public int getTotalSpendTime(String[] cities) {
        if(cities.length > 100000) throw new IllegalArgumentException("도시의 수는 100,000 보다 클 수 없습니다.");

        int totalTime = 0;
        for (final String city : cities) {
            // 추상화 수준을 맞춤. 직접적인 로직이 없이 메쏘드 호출만 함.
            int index = getIndexFromCache(city);
            arrangeCacheIndex(index, city);
            totalTime += getAdditionalTime(index);
        }
        return totalTime;
    }

    private int getAdditionalTime(int index) {
        if (index != NOT_IN_CACHE) {
            return IN_CACHE_TIME;
        } else {
            return IN_DB_TIME;
        }
    }

    /**
     * LRU 는 최근 사용한 값이 저장되어 재사용되는 것
     * @param indexOfCache
     * @param city
     */
    private void arrangeCacheIndex(int indexOfCache, String city) {
        if (this.cacheSize < 1) return;

        String[] cacheTmp = new String[this.cacheSize];
        cacheTmp[0] = city.toLowerCase();

        int newCacheIndex = 1;
        for (int i = 0; i < cache.length && newCacheIndex < cache.length; i++) {
            if(indexOfCache == i) continue;
            cacheTmp[newCacheIndex] = cache[i];
            newCacheIndex++;
        }

        cache = cacheTmp;
    }

    private int getIndexFromCache(final String city) {
        for (int i = 0; i < cache.length; i++) {
            if (StringUtils.equals(cache[i], city)) return i;
        }
        return NOT_IN_CACHE;
    }
}

C# 입니다. Dictionary를 이용, 문자열을 캐싱해서 해결했습니다.

// 핵심 코드
namespace CodingTest
{
    class Cache
    {
        const string NameValidPattern = @"^[a-z]{1,20}$";

        public static int Calc(int cacheSize, string[] cities)
        {
            // 캐시 사이즈가 올바른지 체크합니다.
            if(cacheSize <0 || cacheSize > 30)
            {
                throw new Exception("'cacheSize' is not valid. 'cacheSize' can not exceed 30 and greater then negative value.");
            }
            // 배열범위가 올바른지 체크합니다.
            if(cities.Length > 100000)
            {
                throw new Exception("'cities' array's length can not greater then 100,000");
            }

            int time = 0;
            const int CacheHitTime = 1;
            const int CacheMissTime = 5;

            // 키는 도시 이름, 값은 가장 최근의 인덱스를 포함합니다.
            Dictionary<string,int> cache = new Dictionary<string, int>();

            for (int i = 0; i < cities.Length; i++)
            {
                var city = cities[i].ToLower();
                // 도시의 이름은 20자를 넘을 수 없고 공백, 특수문자, 숫자를 포함하지 않는 영문자만 받습니다.
                if (!Regex.IsMatch(city, NameValidPattern))
                { 
                    throw new Exception("city name have to include only english and can not exceed 20 letters.");
                }

                if (cache.ContainsKey(city))
                {
                    time += CacheHitTime;
                    cache[city] = i;
                }
                else
                {
                    time += CacheMissTime;
                    if (cache.Count < cacheSize)
                    {
                        cache.Add(city,i);
                    }
                    else
                    {
                        if(cacheSize == 0)
                        {
                            continue;
                        }
                        string leastKey = null;
                        int leastValue = 0;
                        // 루프를 돌면서 가장 인덱스가 낮은 값을 찾습니다.
                        foreach(var cacheInfo in cache)
                        {
                            if (leastKey == null)
                            {
                                leastKey = cacheInfo.Key;
                                leastValue = cacheInfo.Value;
                                continue;
                            }
                            if (leastValue > cacheInfo.Value)
                            {
                                leastKey = cacheInfo.Key;
                                leastValue = cacheInfo.Value;
                            }
                        }
                        //가장 인덱스가 낮은 키를 지우고 새로 추가합니다.
                        cache.Remove(leastKey);
                        cache.Add(city, i);
                    }
                }
            }
            return time;
        }
    }
}

//결과 출력
namespace CodingTest
{
    class Program
    {
        const string CacheSize = "cacheSize : ";
        const string Cities = ", cities : ";
        const string ExecutionTime = ", execution : ";

        static void Main(string[] args)
        {
            int cacheSize1 = 3;
            string[] cities1 = new string[] { "Jeju", "Pangyo", "Seoul", "NewYork", "LA", "Jeju", "Pangyo", "Seoul", "NewYork", "LA" };
            PrintCacheFormat(cacheSize1,cities1,Cache.Calc(cacheSize1,cities1));
            int cacheSize2 = 3;
            string[] cities2 = new string[] { "Jeju", "Pangyo", "Seoul", "Jeju", "Pangyo", "Seoul", "Jeju", "Pangyo", "Seoul" };
            PrintCacheFormat(cacheSize2, cities2, Cache.Calc(cacheSize2, cities2));
            int cacheSize3 = 2;
            string[] cities3 = new string[] { "Jeju", "Pangyo", "Seoul", "NewYork", "LA", "SanFrancisco", "Seoul", "Rome", "Paris", "Jeju", "NewYork", "Rome" };
            PrintCacheFormat(cacheSize3, cities3, Cache.Calc(cacheSize3, cities3));
            int cacheSize4 = 0;
            string[] cities4 = new string[]{"Jeju", "Pangyo", "Seoul", "NewYork", "LA"};
            PrintCacheFormat(cacheSize4, cities4, Cache.Calc(cacheSize4, cities4));
        }

        static void PrintCacheFormat(int cacheSize,string[] names,int execution)
        {
            StringBuilder builder = new StringBuilder();
            builder.Append(CacheSize);
            builder.Append(cacheSize);
            builder.Append(Cities);
            builder.Append('[');
            for (int i = 0; i < names.Length; i++)
            {
                builder.Append(names[i]);
                if (i != names.Length - 1)
                {
                    builder.Append(',');
                }
                else
                {
                    builder.Append(']');
                }
            }
            builder.Append(ExecutionTime);
            builder.Append(execution);
            var result = builder.ToString();
            Console.WriteLine(result);
        }
    }
}

package test;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class KakaoTest {

    public static void main(String[] args) {
        int CACHE_TIME = 1;
        int NONE_CACHE_TIME = 5;
        int[] cacheSizes = {3,3,2,5,2,0};

        List<List> citiesList = new ArrayList();
        citiesList.add(Arrays.asList(new String[]{"Jeju", "Pangyo", "Seoul", "NewYork", "LA", "Jeju", "Pangyo", "Seoul", "NewYork", "LA"}));
        citiesList.add(Arrays.asList(new String[]{"Jeju", "Pangyo", "Seoul", "Jeju", "Pangyo", "Seoul", "Jeju", "Pangyo", "Seoul"}));
        citiesList.add(Arrays.asList(new String[]{"Jeju", "Pangyo", "Seoul", "NewYork", "LA", "SanFrancisco", "Seoul", "Rome", "Paris", "Jeju", "NewYork", "Rome"}));
        citiesList.add(Arrays.asList(new String[]{"Jeju", "Pangyo", "Seoul", "NewYork", "LA", "SanFrancisco", "Seoul", "Rome", "Paris", "Jeju", "NewYork", "Rome"}));
        citiesList.add(Arrays.asList(new String[]{"Jeju", "Pangyo", "NewYork", "newyork"}));
        citiesList.add(Arrays.asList(new String[]{"Jeju", "Pangyo", "Seoul", "NewYork", "LA"}));

        for(int i=0; i<citiesList.size(); i++){
            int cacheSize = cacheSizes[i];

            List<String> cache   = new ArrayList();
            List<String> arrCity = citiesList.get(i);

            int delayTime = 0;
            for(String city : arrCity){
                if(cache.contains(city.toLowerCase())) delayTime += CACHE_TIME;
                else {
                    delayTime += NONE_CACHE_TIME;
                    if(cache.size() > cacheSize){
                        cache.remove(0);
                    }
                    cache.add(city.toLowerCase());
                }
            }

            System.out.println("캐시크기 : " + cacheSize + ", 도시이름 : " + arrCity.toString() + ", 실행시간 : " + delayTime);
        }
    }
}

cache_list = []


def lru_cache(size, value):

    if len(cache_list) < size and value not in cache_list:
        cache_list.append(value)
        return 5

    if len(cache_list) >= size and value not in cache_list:
        if len(cache_list):
            cache_list.pop(0)
        cache_list.append(value)
        return 5

    if len(cache_list) < size and value in cache_list:
        cache_list.remove(value)
        cache_list.append(value)
        return 1

    if len(cache_list) >= size and value in cache_list:
        if len(cache_list):
            cache_list.pop(0)
        cache_list.append(value)
        return 1

    return 999


def iteration(val):
    cache_list.clear()

    sum_value = 0
    size = val[0]
    for i in val[1]:
        sum_value += lru_cache(size, i.lower())

    print(sum_value)


iteration([3,['Jeju', 'Pangyo', 'Seoul', 'NewYork', 'LA', 'Jeju', 'Pangyo', 'Seoul', 'NewYork', 'LA']])
iteration([3,['Jeju', 'Pangyo', 'Seoul', 'Jeju', 'Pangyo', 'Seoul', 'Jeju', 'Pangyo', 'Seoul']])
iteration([2,['Jeju', 'Pangyo', 'Seoul', 'NewYork', 'LA', 'SanFrancisco', 'Seoul', 'Rome', 'Paris', 'Jeju', 'NewYork', 'Rome']])
iteration([5,['Jeju', 'Pangyo', 'Seoul', 'NewYork', 'LA', 'SanFrancisco', 'Seoul', 'Rome', 'Paris', 'Jeju', 'NewYork', 'Rome']])
iteration([2,['Jeju', 'Pangyo', 'NewYork', 'newyork']])
iteration([0,['Jeju', 'Pangyo', 'Seoul', 'NewYork', 'LA']])

package codingdojang;

import java.util.ArrayList;
import java.util.Scanner;

public class ex153 {

    public static void main(String[] args) {
        // TODO Auto-generated method stub
        Scanner sc = new Scanner(System.in);

        int size = sc.nextInt(); sc.nextLine();
        String arr[] = {"Jeju", "Pangyo", "Seoul", "NewYork", "LA", "Jeju", "Pangy", "Seoul", "NewYork", "LA"};

        ArrayList<String> cache = new ArrayList<String>();
        int hit = 0; // cache hit 수
        int miss = 0; // cache miss 수 
        boolean same = false;

        for(int i=0; i<size; i++) {
            cache.add(arr[i]);
            miss++;
        }

        for(int i=size; i<arr.length; i++) {
            for(int j=0; j<cache.size(); j++) {
                if(arr[i] == cache.get(j)) {
                    String temp = cache.get(j);
                    cache.remove(j);
                    cache.add(temp);
                    hit++;
                    same = true;
                    break;
                }
                same = false;
            }
            if(!same) {
                cache.remove(0);
                cache.add(arr[i]);
                miss++;
            }
        }

        for(int i=0; i<cache.size(); i++) {
            System.out.println(cache.get(i));
        }

        System.out.println(hit+(5*miss));

    }

}

파이썬 3.6입니다. LRU 캐시가 가장 최근에 쓰인 것부터 찾는 거라고 이해하고 작성했습니다.

def cache(cacheSize:int, cities:[str]) -> int:
    assert 0 <= cacheSize <= 30, "Invalid Cache Size"
    c = [None] * size
    elapsed = 0
    for city in cities:
        _city = city.lower()
        print(c)
        for i, e in enumerate(c):
            if e == _city:
                elapsed += 1
                c = [_city] + c[:i] + c[i+1:]
                break
        else:
            elapsed += 5
            c = c[1:] + [_city]
    return elapsed

def hi(cities, cache_size):
    cache =[] 
    time=0
    for city in cities:
        if city.lower() in cache : 
            cache += [city.lower()]
            time += 1
            cache.pop(cache.index(city.lower()))
        elif city.lower() not in cache :
            cache += [city.lower()]
            time += 5
            if len(cache)>cache_size : cache.pop(0)
    return(time)

python 3.52 입니다

JavaScript로 풀었는데 기타로 분류되네요... ?!

const measureTime = (size, arr) => {
  const cache = [];
  const getFromCache = city => {
    city = city.toLowerCase();
    let time = 0;
    let exists = cache.indexOf(city);
    if (exists !== -1) {
      time = 1;
      cache.splice(exists, 1);
      cache.push(city);
    } else {
      time = 5;
      if (cache.length >= size) {
        cache.shift();
      }
      cache.push(city);
    }

    return time;
  };

  return arr.reduce((s, v) => s += getFromCache(v), 0);
};

console.log(measureTime(3, ['Jeju', 'Pangyo', 'Seoul', 'NewYork', 'LA', 'Jeju', 'Pangyo', 'Seoul', 'NewYork', 'LA']));
console.log(measureTime(3, ['Jeju', 'Pangyo', 'Seoul', 'Jeju', 'Pangyo', 'Seoul', 'Jeju', 'Pangyo', 'Seoul']));
console.log(measureTime(2, ['Jeju', 'Pangyo', 'Seoul', 'NewYork', 'LA', 'SanFrancisco', 'Seoul', 'Rome', 'Paris', 'Jeju', 'NewYork', 'Rome']));
console.log(measureTime(5, ['Jeju', 'Pangyo', 'Seoul', 'NewYork', 'LA', 'SanFrancisco', 'Seoul', 'Rome', 'Paris', 'Jeju', 'NewYork', 'Rome']));
console.log(measureTime(2, ['Jeju', 'Pangyo', 'NewYork', 'newyork']));
console.log(measureTime(0, ['Jeju', 'Pangyo', 'Seoul', 'NewYork', 'LA']));

파이썬 3.6입니다.

def LRUtime(cachesize, cities):
    if cachesize < 0  or cachesize > 30:
        print("cachesize는 0~30사이로 입력하세요.")
        return

    if len(cities) > 100000:
        print("도시 갯수는 최대 10,000개 입니다.")
        return

    # 작업 변수 정의
    cache = []
    time_cache_hit  = 1
    time_cache_miss = 5
    run_time        = 0

    for city in cities:
        city_str = city.upper()

        # Caching작업 : LRU(Least Recently Used)
        if city_str in cache:
            cache.remove(city_str)
            cache.append(city_str)
            run_time += time_cache_hit
        elif cachesize > 0:
            if len(cache) == cachesize:
                del cache[0]
            cache.append(city_str)
            run_time += time_cache_miss
        else: # cachesize가 0일때는 Caching작업 안함
            run_time += time_cache_miss
    return run_time

Haskell

import Data.Char (toUpper)
import Data.List (delete)

solution :: Int -> [String] -> Int 
solution cacheSize = sum
                   . fmap cost
                   . (zipWith (flip elem)
                          =<< scanl updateCache [])
                   . fmap (fmap toUpper)
    where
        updateCache cache v = take cacheSize
                            $ v : delete v cache

        cost True = 1
        cost False = 5

main = print $ solution 5 ["Jeju", "Pangyo", "Seoul", "NewYork", "LA", "SanFrancisco", "Seoul", "Rome", "Paris", "Jeju", "NewYork", "Rome"]

Python3

def funcLRU(cacheSize, cities):
    if not(0 <= cacheSize <= 30):
        print('에러:cache의 size를 벗어남')
        return
    if not(0 < len(cities) <= 100000):
        print('에러:도시의 개수를 벗어남')
        return
    citiesLower = []
    for citi in cities:
        if not(0 < len(citi) <= 20): 
            print('에러:도시 이름은 20자 이하여야 합니다.')
            return
        if not(citi.isalpha()):
            print('에러:도시 이름은 공백, 숫자, 특수문자 등이 없는 영문자여야 합니다.')
            return
        citiesLower.append(citi.lower())
    if (cacheSize == 0):
        print(len(cities)*5)
        return
    citiesCache= []
    runtime = 0 
    for citi in citiesLower:
        if citi in citiesCache:
            runtime += 1
            citiesCache.remove(citi)
            citiesCache.append(citi)
        else:
            runtime += 5
            if (len(citiesCache) == cacheSize):
                del citiesCache[0]
                citiesCache.append(citi)
            else:
                citiesCache.append(citi)
    print(runtime)

testCases = [
    [3, ['Jeju', 'Pangyo', 'Seoul', 'NewYork', 'LA', 'Jeju', 'Pangyo', 'Seoul', 'NewYork', 'LA']],
    [3, ['Jeju', 'Pangyo', 'Seoul', 'Jeju', 'Pangyo', 'Seoul', 'Jeju', 'Pangyo', 'Seoul']],
    [2, ['Jeju', 'Pangyo', 'Seoul', 'NewYork', 'LA', 'SanFrancisco', 'Seoul', 'Rome', 'Paris', 'Jeju', 'NewYork', 'Rome']],
    [5, ['Jeju', 'Pangyo', 'Seoul', 'NewYork', 'LA', 'SanFrancisco', 'Seoul', 'Rome', 'Paris', 'Jeju', 'NewYork', 'Rome']],
    [2, ['Jeju', 'Pangyo', 'NewYork', 'newyork']],
    [0, ['Jeju', 'Pangyo', 'Seoul', 'NewYork', 'LA']],
    [31, ['Jeju', 'Pangyo', 'Seoul', 'NewYork', 'LA']],
    [0, ['Jej*', 'Pangyo', 'Seoul', 'NewYork', 'LA']],
    [0, ['Jejddddddddddddddddddddddddddddddddddddddddddddd']]
]
for testCase in testCases:
    funcLRU(testCase[0], testCase[1])

예시는 코드 내에서 변경하면서 테스트해봤습니다.

package test;

import java.util.Stack;

public class lru {
    static int CACHE_SIZE = 3;
    public static void main(String[] args) {
        String[] list =  {"Jeju", "Pangyo", "Seoul", "Jeju", "Pangyo", "Seoul", "Jeju", "Pangyo", "Seoul"}; 
        Stack<String> st = new Stack<String>();
        int processCount = 0;

        for(int i = 0; i < list.length ; i++){
            if(st.remove(list[i])){
                processCount += 1;
            }else{
                if(st.size() >= CACHE_SIZE)
                    st.remove(0);
                processCount += 5;
            }
            st.push(list[i]);
        }

        System.out.println("실행시간 : " + processCount);
    }
}

캐시는 list로 하고 hit되면 가장 앞으로 보내서 LRU 동작을 구현하였습니다.

inputs = [{"cacheSize": 3, "cities": ["Jeju", "Pangyo", "Seoul", "NewYork", "LA", "Jeju", "Pangyo", "Seoul", "NewYork", "LA"], "result": 50},
          {"cacheSize": 3, "cities":  ["Jeju", "Pangyo", "Seoul", "Jeju", "Pangyo", "Seoul", "Jeju", "Pangyo", "Seoul"], "result": 21},
          {"cacheSize": 2, "cities": ["Jeju", "Pangyo", "Seoul", "NewYork", "LA", "SanFrancisco", "Seoul", "Rome", "Paris", "Jeju", "NewYork", "Rome"], "result": 60},
          {"cacheSize": 5, "cities": ["Jeju", "Pangyo", "Seoul", "NewYork", "LA", "SanFrancisco", "Seoul", "Rome", "Paris", "Jeju", "NewYork", "Rome"], "result": 52},
          {"cacheSize": 2, "cities": ["Jeju", "Pangyo", "NewYork", "newyork"], "result": 16},
          {"cacheSize": 0, "cities":  ["Jeju", "Pangyo", "Seoul", "NewYork", "LA"], "result": 25}]


def loadCities(cacheSize, cities):
    elapsed = 0
    caches = []
    for _city in cities:
        city = _city.lower()
        if city in caches:
            caches.remove(city)
            caches.insert(0, city)
            elapsed += 1
        else:
            if cacheSize > 0 and len(caches) == cacheSize:
                caches.pop()
            caches.insert(0, city)
            elapsed += 5

    return elapsed


for input in inputs:
    cachesize = input["cacheSize"]
    cities = input["cities"]
    result = input["result"]
    assert(loadCities(cachesize, cities) == result)

N =5
cache = [ 0 for i in range(0,N)]
cost = 0
inputs = ['Jeju', 'Pangyo', 'Seoul', 'NewYork', 'LA', 'SanFrancisco', 'Seoul', 'Rome','Paris', 'Jeju', 'NewYork', 'Rome']
for i in inputs:
    if i in cache: cost = cost + 1
    else:
        cache = [i] + cache[0:N-1]
        cost = cost + 5

파이썬 3.6

def runtime(cache,data):
    result,count,used = 0,0,[]
    for index,i in enumerate(data):
        if cache == 0: # cache miss
            result += 5
        elif len(used) < cache and i.lower() not in used: # cache miss
            used.append(i.lower())
            result += 5
        elif i.lower() not in used: # cache miss
            del used[0]
            used.append(i.lower())
            result += 5
        elif i.lower() in used: # cache hit
            used.remove(i.lower())
            used.append(i.lower())
            result += 1
    return result

if __name__ == "__main__":
    dataset = [[3,['Jeju', 'Pangyo', 'Seoul', 'NewYork', 'LA', 'Jeju', 'Pangyo', 'Seoul', 'NewYork', 'LA']],           
              [3,['Jeju', 'Pangyo', 'Seoul', 'Jeju', 'Pangyo', 'Seoul', 'Jeju', 'Pangyo', 'Seoul']],
              [2,['Jeju', 'Pangyo', 'Seoul', 'NewYork', 'LA', 'SanFrancisco', 'Seoul', 'Rome', 'Paris', 'Jeju', 'NewYork', 'Rome']],
              [5,['Jeju', 'Pangyo', 'Seoul', 'NewYork', 'LA', 'SanFrancisco', 'Seoul', 'Rome', 'Paris', 'Jeju', 'NewYork', 'Rome']],
              [2,['Jeju', 'Pangyo', 'NewYork', 'newyork']],
              [0,['Jeju', 'Pangyo', 'Seoul', 'NewYork', 'LA']]]
    for data in dataset:
        print(data[0],data[1],runtime(data[0],data[1]))

• 결과값

3 ['Jeju', 'Pangyo', 'Seoul', 'NewYork', 'LA', 'Jeju', 'Pangyo', 'Seoul', 'NewYork', 'LA'] 50
3 ['Jeju', 'Pangyo', 'Seoul', 'Jeju', 'Pangyo', 'Seoul', 'Jeju', 'Pangyo', 'Seoul'] 21
2 ['Jeju', 'Pangyo', 'Seoul', 'NewYork', 'LA', 'SanFrancisco', 'Seoul', 'Rome', 'Paris', 'Jeju', 'NewYork', 'Rome'] 60
5 ['Jeju', 'Pangyo', 'Seoul', 'NewYork', 'LA', 'SanFrancisco', 'Seoul', 'Rome', 'Paris', 'Jeju', 'NewYork', 'Rome'] 52
2 ['Jeju', 'Pangyo', 'NewYork', 'newyork'] 16
0 ['Jeju', 'Pangyo', 'Seoul', 'NewYork', 'LA'] 25

package solr.example.solr.example;

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;

public class CacheMemory {

    public static void main(String[]args) throws Exception{
        BufferedReader br =new BufferedReader(new InputStreamReader(System.in));
        System.out.println("Cache Size");

        int cache = Integer.valueOf(br.readLine());

        List<String> cities = new ArrayList<String>();
        List<String> caches = new ArrayList<String>();
        int hit = 0;
        int miss = 0;
        int cac = 0;
        while(true) {
            String city = br.readLine();
            if(caches.contains(city)) {
                hit++;
            }else {
                caches.add(city);
                miss++;
                if(caches.size()>cache) {
                    caches.remove(0);
                }
            }
            cities.add(city);
            if(cities.size()>100000) {
                cities.remove(0);
            }
            System.out.println("캐시 사이즈="+cache+"\r도시="+cities.toString());
            System.out.println("소요시간="+(hit+(miss*5)));
        }
    }

}

입력 리스트길이가 1,000,000일때 1초 내외로 답이 출력됩니다.

def cache(a, n):
    cache = [0 for i in range(n)]
    time = 0
    for i in a:
        i = i.lower()
        if i in cache:
            cache.remove(i)
            cache.append(i)
            time += 1
        else:
            cache.append(i)
            cache.pop(0)
            time += 5
    return time

func citiesSearchFn(_ cachSize: Int, _ cities: [String]) -> Int {
    var usedTime = 0

    guard  0 ... 30 ~= cachSize else {
        return -1
    }

    guard cities.count < 100000 else {
        return -2
    }

    var lowercaseCities: Array<String> = cities.map{ $0.lowercased() }
    var cachArray = Array<String>(repeating: "", count: cachSize)
    for (idx, city) in lowercaseCities.enumerated() where idx < cachArray.count  {
        cachArray[idx] = city
        usedTime += 5
    }

    for city in lowercaseCities[cachSize...] where cachArray.count > 0 {
        // 캐시에 값이 있을 경우
        if cachArray.contains(city) {
            usedTime += 1
        } else {
            //캐시에 값이 없을 경우,
            usedTime += 5
            cachArray.removeFirst()
            cachArray.append(city)
        }
    }

    if cachArray.count == 0 {
        usedTime = 5 * cities.count
    }

    return usedTime
}

스위프트 4 입니다.

public static void main(String[] args) {
        int cacheSize = 3;
        String[] cites = new String[]{"Jeju", "Pangyo", "Seoul", "NewYork", "LA", "Jeju",
                                    "Pangyo", "Seoul", "NewYork", "LA"};

        int result = calRuntime(cacheSize, cites);
        System.out.println(result);

        cacheSize = 3;
        cites = new String[]{"Jeju", "Pangyo", "Seoul", "Jeju", "Pangyo", "Seoul", "Jeju",
                "Pangyo", "Seoul"};

        result = calRuntime(cacheSize, cites);
        System.out.println(result);

        cacheSize = 2;
        cites = new String[]{"Jeju", "Pangyo", "Seoul", "NewYork", "LA", "SanFrancisco",
                "Seoul", "Rome", "Paris", "Jeju", "NewYork", "Rome"};

        result = calRuntime(cacheSize, cites);
        System.out.println(result);

        cacheSize = 5;
        cites = new String[]{"Jeju", "Pangyo", "Seoul", "NewYork", "LA", "SanFrancisco",
                "Seoul", "Rome", "Paris", "Jeju", "NewYork", "Rome"};

        result = calRuntime(cacheSize, cites);
        System.out.println(result);

        cacheSize = 2;
        cites = new String[]{"Jeju", "Pangyo", "NewYork", "newyork"};

        result = calRuntime(cacheSize, cites);
        System.out.println(result);

        cacheSize = 0;
        cites = new String[]{"Jeju", "Pangyo", "Seoul", "NewYork", "LA"};

        result = calRuntime(cacheSize, cites);
        System.out.println(result);
    }

    public static int calRuntime(int cacheSize, String[] cites) {
        int runtime = 0;
        Queue cacheQueue = new LinkedList();
        for(String city : cites) {
            if(cacheSize == 0) {
                runtime += 5;
                continue;
            }

            if(cacheQueue.size() < cacheSize) {
                cacheQueue.add(city.toLowerCase());
                runtime += 5;
            }
            else {
                if(cacheQueue.contains(city.toLowerCase())) {
                    cacheQueue.remove(city.toLowerCase());
                    cacheQueue.add(city.toLowerCase());
                    runtime++;

                } else {
                    cacheQueue.poll();
                    cacheQueue.add(city.toLowerCase());
                    runtime += 5;
                }
            }
        }
        return runtime;
    }

queue의 특성을 이용한 구현으로 quque에 값이 없는 경우 마지막으로 사용된 값을 내보내고 +5
값이 있는 경우 마지막으로 사용된 값을 내보내고 새로 추가한 다음 +1

대소문자 구분없게 하기위해 전부 lower String으로 저장 틀린점있으면 댓글 부탁드립니다.

def LRU_timer(size, items):
    cache = []
    time = 0
    for item in items:
        item = item.lower()
        if item in cache:
            time += 1
            cache.remove(item)
            cache.append(item)
        else:
            time += 5
            cache.append(item)
        if len(cache) > size: del cache[0]
    return time

cachesize = [3,3,2,5,2,0]
test = [['Jeju', 'Pangyo', 'Seoul', 'NewYork', 'LA', 'Jeju', 'Pangyo', 'Seoul', 'NewYork', 'LA'], ['Jeju', 'Pangyo', 'Seoul', 'Jeju', 'Pangyo', 'Seoul', 'Jeju', 'Pangyo', 'Seoul'], ['Jeju', 'Pangyo', 'Seoul', 'NewYork', 'LA', 'SanFrancisco', 'Seoul', 'Rome', 'Paris', 'Jeju', 'NewYork', 'Rome'], ['Jeju', 'Pangyo', 'Seoul', 'NewYork', 'LA', 'SanFrancisco', 'Seoul', 'Rome', 'Paris', 'Jeju', 'NewYork', 'Rome'], ['Jeju', 'Pangyo', 'NewYork', 'newyork'], ['Jeju', 'Pangyo', 'Seoul', 'NewYork', 'LA']]
for i in range(len(cachesize)):
    print('{} {} {}'.format(cachesize[i],test[i],LRU_timer(cachesize[i],test[i])))

3 ['Jeju', 'Pangyo', 'Seoul', 'NewYork', 'LA', 'Jeju', 'Pangyo', 'Seoul', 'NewYork', 'LA'] 50
3 ['Jeju', 'Pangyo', 'Seoul', 'Jeju', 'Pangyo', 'Seoul', 'Jeju', 'Pangyo', 'Seoul'] 21
2 ['Jeju', 'Pangyo', 'Seoul', 'NewYork', 'LA', 'SanFrancisco', 'Seoul', 'Rome', 'Paris', 'Jeju', 'NewYork', 'Rome'] 60
5 ['Jeju', 'Pangyo', 'Seoul', 'NewYork', 'LA', 'SanFrancisco', 'Seoul', 'Rome', 'Paris', 'Jeju', 'NewYork', 'Rome'] 52
2 ['Jeju', 'Pangyo', 'NewYork', 'newyork'] 16
0 ['Jeju', 'Pangyo', 'Seoul', 'NewYork', 'LA'] 25

import java.text.*;
import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc=new Scanner(System.in);
        List<String>cache=new ArrayList<String>();
        List<Integer>index_list=new ArrayList<Integer>();

        while(true) {
            System.out.println("캐쉬 크기를 입력하세요.");
            int cache_size=sc.nextInt();
            sc.nextLine();
            System.out.println("도시들을 입력하세요.");
            String[] cities=sc.nextLine().split(" ");


            if(cache.isEmpty()) {
                for(int i=0;i<cache_size;i++) {
                    cache.add(cities[cities.length-(i+1)]);
                }
            }else if(cache.size()>cache_size) {
                List<Integer>indices=new ArrayList<Integer>();
                for(int i=cache_size;i<cache.size();i++) {
                    cache.remove(i);
                }
                for(int i=cache_size;i>0;i--) {
                    if(cache.contains(cities[cities.length-i])) {
                        cache.remove(cities[cities.length-i]);
                        cache.add(0, cities[cities.length-i]);
                    }else {
                        cache.remove(cache.size()-1);
                        cache.add(0, cities[cities.length-i]);
                    }
                }
                for(int i=cache_size;i<cache.size();i++) {
                    cache.remove(cache_size);
                }
            }else if(cache.size()<=cache_size) {
                for(int i=cache_size;i>0;i--) {
                    if(!cache.contains(cities[cities.length-i])) {
                        if(cache.size()>=cache_size) {
                            cache.remove(cache.size()-1);
                            cache.add(0, cities[cities.length-i]);
                        }else {
                            cache.add(0, cities[cities.length-i]);
                        }
                    }else if(cache.contains(cities[cities.length-i])) {
                        cache.remove(cities[cities.length-i]);
                        cache.add(0, cities[cities.length-i]);
                    }
                }
            }
            System.out.println(cache);
        }
    }
}

class LRUList {
        private List<String> list;
        private int listSize;

        public LRUList(int listSize) {
            list = new LinkedList<String>();
            this.listSize = listSize;
        }

        public boolean reference(String city) {
            if (this.listSize == 0)
                return false;

            if (list.contains(city)) {
                list.remove(city);
                list.add(city);
                //System.out.println(list.toString());
                return true;
            } else {
                if (list.size() == this.listSize)
                    list.remove(0);

                list.add(city);
                //System.out.println(list.toString());
                return false;
            }
        }
}

public class Javatutorial {
    // hit: 1T, miss:5T
    public static int run(int cacheSize, String[] cities) {
        LRUList list = new LRUList(cacheSize);
        int runningTime = 0;

        for (String city : cities) {        
            if (list.reference(city))
                runningTime += 1;
            else
                runningTime += 5;
        }
        return runningTime;
    }

    public static void main(String[] args) {
        int[] cacheSize = {3, 3, 2, 5, 2, 0};
        String[][] cities = {
                {"Jeju", "Pangyo", "Seoul", "NewYork", "LA", "Jeju", "Pangyo", "Seoul", "NewYork", "LA"},
                {"Jeju", "Pangyo", "Seoul", "Jeju", "Pangyo", "Seoul", "Jeju", "Pangyo", "Seoul"},
                {"Jeju", "Pangyo", "Seoul", "NewYork", "LA", "SanFrancisco", "Seoul", "Rome", "Paris", "Jeju", "NewYork", "Rome"},
                {"Jeju", "Pangyo", "Seoul", "NewYork", "LA", "SanFrancisco", "Seoul", "Rome", "Paris", "Jeju", "NewYork", "Rome"},
                {"Jeju", "Pangyo", "NewYork", "newyork"},
                {"Jeju", "Pangyo", "Seoul", "NewYork", "LA"}
                };

        for (int i = 0; i < cacheSize.length; i++) {
                System.out.println(run(cacheSize[i], cities[i]));               
        }
    }
}

#include<iostream>
#include<string>
#include<list>
using namespace std;
#pragma warning(disable:4996) //strcmp등 고대(?)함수 사용에러 무시

int main()
{
    int cacheSize;
    cout << "cache size : ";
    cin >> cacheSize;

    int runTime = 0;

    list<string> cache;
    list<string> cities;

    //도시이름 입력
    while (true)
    {
        string str;

        cout << "도시 입력 : (exit를 입력하면 종료)";
        cin >> str;

        if (str == "exit")
        {
            break;
        }
        cities.push_back(str);
    }

    list<string>::iterator cityIt;

    //캐시에서 도시 찾기
    cache.push_back(*cities.begin());
    runTime += 4;

    for (cityIt = cities.begin(); cityIt != cities.end(); cityIt++)
    {
        list<string>::iterator cacheIt;
        bool search = false;
        cout << "?" << endl;

        for (cacheIt = cache.begin(); cacheIt != cache.end(); cacheIt++)
        {
            string cacheStr = *cacheIt;
            string cityStr = *cityIt;

            //대소문자 구분없이 비교 함수
            if (!strcmpi(cacheStr.c_str(), cityStr.c_str()))
            {
                cout << *cacheIt << endl;
                cacheIt->swap(*cities.begin());
                search = true;
                runTime++;
                break;
            }
        }
        if (!search)//캐시에 없으면
        {
            runTime += 5;
            cache.push_front(*cityIt);
            if (cache.size() > cacheSize) //캐시 사이즈 넘어가면
            {
                cache.pop_back();
            }
        }
    }

    cout << runTime;
}

swift 입니다. 더 효율적인 방법이 있다면 알려주세요!

class Question3 {
// 3. 캐시(난이도: 하)
  static func execute(_ cacheSize: Int,
                      _ cities: [String]) -> Int {
    if cacheSize == 0 {
      return cities.count * 5
    }

    var cacheTable = [String]()
    let lowerCities = cities.map{$0.lowercased()}

    var executedTime = 0

    for city in lowerCities {
      if cacheTable.contains(city) {
        executedTime += 1
      } else {
        if cacheTable.count != cacheSize {
          cacheTable.append(city)
        } else {
          cacheTable = Array(cacheTable[1..<cacheTable.count - 1])
          cacheTable.append(city)
        }
        executedTime += 5
      }

    }

    return executedTime
  }

  static func test01() -> Bool {
    let cities1 = ["Jeju", "Pangyo", "Seoul", "NewYork", "LA", "Jeju", "Pangyo", "Seoul", "NewYork", "LA"]

    return execute(3, cities1) == 50
  }

  static func test02() -> Bool {
    let cities2 = ["Jeju", "Pangyo", "Seoul", "Jeju", "Pangyo", "Seoul", "Jeju", "Pangyo", "Seoul"]

    return execute(3, cities2) == 21
  }

  static func test03() -> Bool {
    let cities3 = ["Jeju", "Pangyo", "Seoul", "NewYork", "LA", "SanFrancisco", "Seoul", "Rome", "Paris", "Jeju", "NewYork" , "Rome"]

    return execute(2, cities3) == 60
  }

  static func test04() -> Bool {
     let cities3 = ["Jeju", "Pangyo", "Seoul", "NewYork", "LA", "SanFrancisco", "Seoul", "Rome", "Paris", "Jeju", "NewYork" , "Rome"]

    return execute(5, cities3) == 52
  }

  static func test05() -> Bool {
    let cities5 = ["Jeju", "Pangyo", "NewYork", "newyork"]

    return execute(2, cities5) == 16
  }

  static func test06() -> Bool {
    let cities6 = ["Jeju", "Pangyo", "Seoul", "NewYork", "LA"]

    return execute(2, cities6) == 25
  }

  static func testAll() -> Bool{
    return test01() &&
      test02() &&
      test03() &&
      test04() &&
      test05() &&
      test06()
  }
}

#include <iostream>
#include <string>
#include <vector>

using namespace std;


int main(void)
{
    int cnt = 0;
    int num;
    string s;
    vector<string> sv;
    getline(cin, s);
    int startpos = 0;
    int finalpos;
    string part[10];
    int time = 0;
    int citynum = 0;
    for (int i = 0; i < s.length(); i++)
    {


        finalpos = s.find(' ', startpos);
        if (finalpos == -1)
        {
            part[i] = s.substr(startpos);
            citynum = i + 1;
            break;
        }
        part[i] = s.substr(startpos, finalpos - startpos);
        startpos = finalpos + 1;
        citynum = i + 1;
    }




    cout << "캐시크기를 입력하시오>>";
    cin >> num;
    for (int i = 0; i < num; i++)
    {
        sv.push_back(part[i]);
        time += 5;
    }
    for (int i = num; i < citynum; i++)
    {
        vector<string>::iterator itr = sv.begin();
        for (; itr < sv.end(); itr++)
        {
            if (*itr == part[i])
            {
                time += 1;
                break;
            }
            else
            {
                cnt++;
            }
        }
        if (cnt ==3) {
            sv.pop_back();
            sv.push_back(part[i]);
            time += 5;


        }
        cnt = 0;
    }
    cout << time << endl;
}

cache_size = int(input())
if cache_size > 30:
    raise Exception('too large cache')

temp_cities = list(input().split())
if len(temp_cities) > 100000:
    raise Exception('too many cities')

cities = []
for i in temp_cities:
    cities.append(i.lower())




def initial_cache(cities, cache_size):
    cache = [cities[0]]
    time = 5
    count = 0
    for i in range(1, cache_size):
        for j in cache:
            if j == cities[i]:
                 count += 1
        if count > 0:
            time += 1
        else:
            time += 5
        cache.append(cities[i])
        count = 0

    return cache, time


def hit_or_miss(cities, cache, cache_size):
    time = 0
    for i in range(cache_size, len(cities)):
        if cities[i] in cache:
            time += 1
        else:
            time += 5

        cache.pop(0)
        cache.append(cities[i])

    return time

if cache_size == 0:
    print(len(cities)*5)
else:
    first_cache, first_time = initial_cache(cities, cache_size)
    print(first_time + hit_or_miss(cities, first_cache, cache_size))

C#
큐(Queue) 자료형을 이용하여 LRU 알고리즘을 구현했습니다.

CLASS

class Cache
    {
        private Queue<string> queue = null;

        private readonly int cacheSize; // 캐시 크기

        public int ProcessTime { get; private set; } = 0; // 실행 시간

        public Cache(int cacheSize)
        {
            this.cacheSize = cacheSize;
            queue = new Queue<string>(cacheSize);
        }

        public void Lru(string str) // LRU 알고리즘
        {
            str = str.ToLower();

            if (cacheSize == 0)
            {
                ProcessTime += 5;
                return;
            }

            if (queue.Contains(str)) // 큐 내에 존재할 경우 순서 갱신
            {
                Queue<string> tmpQueue = new Queue<string>();

                foreach (var item in queue)
                {
                    if (item != str) { tmpQueue.Enqueue(item); }
                }
                tmpQueue.Enqueue(str);
                queue = tmpQueue;
                ProcessTime += 1; // cache hit
            }
            else // 큐 내에 존재하지 않을 경우 추가 (오래된 큐 제거)
            {
                if (queue.Count == cacheSize) { queue.Dequeue(); }
                queue.Enqueue(str);
                ProcessTime += 5; // cache miss
            }
        }

        public static int GetProcessTime(int cacheSize, List<string> aList)
        {
            Cache cc = new Cache(cacheSize);
            foreach (var item in aList)
            {
                cc.Lru(item);
            }
            return cc.ProcessTime;
        }
    }

TEST CASES

using System;
using System.Collections.Generic;

namespace CD152
{
    class Program
    {
        static void Main()
        {
            int cacheSize;
            List<string> cities;

            cacheSize = 3;
            cities = new List<string>()
            { "Jeju", "Pangyo", "Seoul", "NewYork", "LA", "Jeju", "Pangyo", "Seoul", "NewYork", "LA" };
            Console.WriteLine(Cache.GetProcessTime(cacheSize, cities));

            cacheSize = 3;
            cities = new List<string>()
            { "Jeju", "Pangyo", "Seoul", "Jeju", "Pangyo", "Seoul", "Jeju", "Pangyo", "Seoul" };
            Console.WriteLine(Cache.GetProcessTime(cacheSize, cities));

            cacheSize = 2;
            cities = new List<string>()
            { "Jeju", "Pangyo", "Seoul", "NewYork", "LA", "SanFrancisco", "Seoul", "Rome", "Paris", "Jeju",
                "NewYork", "Rome" };
            Console.WriteLine(Cache.GetProcessTime(cacheSize, cities));

            cacheSize = 5;
            cities = new List<string>()
            { "Jeju", "Pangyo", "Seoul", "NewYork", "LA", "SanFrancisco", "Seoul", "Rome", "Paris", "Jeju",
                "NewYork", "Rome" };
            Console.WriteLine(Cache.GetProcessTime(cacheSize, cities));

            cacheSize = 2;
            cities = new List<string>() { "Jeju", "Pangyo", "NewYork", "newyork" };
            Console.WriteLine(Cache.GetProcessTime(cacheSize, cities));

            cacheSize = 0;
            cities = new List<string>() { "Jeju", "Pangyo", "Seoul", "NewYork", "LA" };
            Console.WriteLine(Cache.GetProcessTime(cacheSize, cities));

            Console.ReadKey();
        }
    }
}

파이썬 입니다.

def time_LRU(cache_times, cities):

    if not(0 < cache_times <= 30):
        print("Error: 도시의 캐시 크기를 벗어 났습니다.")
        return
    if not (0 < len(cities) <= 100000):
        print("Error: 도시의 개수를 벗어 났습니다.")
        return

    exec_time = 0
    cache_list = []
    city_lowers = []

    for city in cities:
        if not(0 < len(city) <= 20):
            print("Error: 도시 이름은 20자 이하여야 합니다.")
            return

        if not(city.isalpha()):
            print("Error: 도시 이름은 문자로만 구성 되어야 합니다.")
            return

        city_lowers.append(city.lower())

    # print(city_lowers)

    for city_var in city_lowers:

        if city_var in cache_list:
            exec_time += 1
            cache_list.remove(city_var)
            cache_list.append(city_var)
        else:
            exec_time += 5
            if len(cache_list) == cache_times:
                del cache_list[0]
                cache_list.append(city_var)
            else:
                cache_list.append(city_var)
    print('exec_time: ' + str(exec_time))

test_case = [
    [3, ['Jeju', 'Pangyo', 'Seoul', 'NewYork', 'LA', 'Jeju', 'Pangyo', 'Seoul', 'NewYork', 'LA']],
    [3, ['Jeju', 'Pangyo', 'Seoul', 'Jeju', 'Pangyo', 'Seoul', 'Jeju', 'Pangyo', 'Seoul']],
    [2, ['Jeju', 'Pangyo', 'Seoul', 'NewYork', 'LA', 'SanFrancisco', 'Seoul', 'Rome', 'Paris', 'Jeju', 'NewYork', 'Rome']],
    [5, ['Jeju', 'Pangyo', 'Seoul', 'NewYork', 'LA', 'SanFrancisco', 'Seoul', 'Rome', 'Paris', 'Jeju', 'NewYork', 'Rome']],
    [2, ['Jeju', 'Pangyo', 'NewYork', 'newyork']],
    [0, ['Jeju', 'Pangyo', 'Seoul', 'NewYork', 'LA']],
    [31,    ['Jeju', 'Pangyo', 'Seoul', 'NewYork', 'LA']],
    [1, ['Jeju**', 'Pangyo', 'Seoul', 'NewYork', 'LA']],
    [1, ['dddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddd']]
]

for case in test_case:
    time_LRU(case[0], case[1])

using System;
using System.Collections.Generic;

namespace solution
{
    class Program
    {
        static void Main(string[] args)
        {
            //string[] cities = new string[]{"Jeju", "Pangyo", "Seoul", "NewYork", "LA", "Jeju", "Pangyo", "Seoul", "NewYork", "LA"};
            //int cacheSize = 3;

            //string[] cities = new string[] { "Jeju", "Pangyo", "Seoul", "Jeju", "Pangyo", "Seoul", "Jeju", "Pangyo", "Seoul" };
            //int cacheSize = 3;

            //string[] cities = new string[] { "Jeju", "Pangyo", "Seoul", "NewYork", "LA",
            //                "SanFrancisco", "Seoul", "Rome", "Paris", "Jeju", "NewYork", "Rome" };
            //int cacheSize = 2;

            //string[] cities = new string[] { "Jeju", "Pangyo", "Seoul", "NewYork", "LA", "SanFrancisco",
            //                                    "Seoul", "Rome", "Paris", "Jeju", "NewYork", "Rome" };
            //int cacheSize = 5;

            //string[] cities = new string[] { "Jeju", "Pangyo", "NewYork", "newyork" };
            //int cacheSize = 2;

            string[] cities = new string[] { "Jeju", "Pangyo", "Seoul", "NewYork", "LA" };
            int cacheSize = 0;

            Console.WriteLine("\n 실행 시간: {0}", checkRunTime(cacheSize, cities));
        }

        private static int checkRunTime(int cacheSize, string[] cities)
        {
            Queue<string> que = new Queue<string>();
            int runTime = 0;
            for (int i = 0; i < cities.Length; i++)
            {
                string city = cities[i].ToLower();
                if (!que.Contains(city))
                    runTime += 5;
                else
                    runTime += 1;

                que.Enqueue(city);
                if (que.Count > cacheSize)
                    que.Dequeue();
            }
            return runTime;
        }
    }
}