코딩테스트 LRU 캐시: 지도 타일 재사용 기록

function solution(capacity, requests) {
    const map = new Map();
    const head = {
        next : null
    }, tail = {
        prev : head
    };
    head.next = tail;
    const detach = node => {
        node.prev.next = node.next;
        node.next.prev = node.prev;
    };
    const front = node => {
        node.prev = head;
        node.next = head.next;
        head.next.prev = node;
        head.next = node;
    };
    const hits = [];
    for (const key of requests) {
        const node = map.get(key);
        hits.push(node !== undefined);
        if (node) {
            detach(node);
            front(node);
        }
        else if (capacity > 0) {
            if (map.size === capacity) {
                const old = tail.prev;
                detach(old);
                map.delete(old.key);
            }
            const fresh = {
                key
            };
            map.set(key, fresh);
            front(fresh);
        }
    }
    const keys = [];
    for (let node = head.next; node !== tail; node = node.next) keys.push(node.key);
    return {
        hits, keys
    };
}

from collections import OrderedDict

def solution(capacity, requests):
    cache = OrderedDict()
    hits = []
    for key in requests:
        hit = key in cache
        hits.append(hit)
        if hit:
            cache.move_to_end(key)
        elif capacity > 0:
            if len(cache) == capacity:
                cache.popitem(last=False)
            cache[key] = True
    return {"hits": hits, "keys": list(reversed(cache))}

import java.util.*;
class Solution {
    public Map < String, Object > solution(int capacity, String[] requests) {
        LinkedHashMap < String, Boolean > cache = new LinkedHashMap < >(16, 0.75f, true);
        List < Boolean > hits = new ArrayList < >();
        for (String key : requests) {
            boolean hit = cache.get(key) != null;
            hits.add(hit);
            if (! hit && capacity > 0) {
                if (cache.size() == capacity) {
                    Iterator < String > it = cache.keySet().iterator();
                    it.next();
                    it.remove();
                }
                cache.put(key, true);
            }
        }
        List < String > keys = new ArrayList < >(cache.keySet());
        Collections.reverse(keys);
        Map < String, Object > result = new HashMap < >();
        result.put("hits", hits);
        result.put("keys", keys);
        return result;
    }
}

#include <algorithm>
#include <array>
#include <functional>
#include <list>
#include <limits>
#include <memory>
#include <numeric>
#include <queue>
#include <string>
#include <unordered_map>
#include <utility>
#include <vector>
using namespace std;
struct Result {
    vector < bool > hits;
    vector < string > keys;
};
Result solution(int capacity, const vector < string > & requests) {
    list < string > order;
    unordered_map < string, list < string >::iterator > cache;
    Result result;
    for (const string & key : requests) {
        auto it = cache.find(key);
        bool hit = it != cache.end();
        result.hits.push_back(hit);
        if (hit) order.splice(order.begin(), order, it->second);
        else if (capacity > 0) {
            if (cache.size() == static_cast < size_t >(capacity)) {
                cache.erase(order.back());
                order.pop_back();
            }
            order.push_front(key);
            cache[key] = order.begin();
        }
    }
    result.keys.assign(order.begin(), order.end());
    return result;
}

using System;
using System.Collections.Generic;
using System.Text;
public class Solution {
    public Dictionary < string, object > Solve(int capacity, string[] requests) {
        var order = new LinkedList < string >();
        var cache = new Dictionary < string, LinkedListNode < string >>(StringComparer.Ordinal);
        var hits = new List < bool >();
        foreach(string key in requests) {
            LinkedListNode < string > node;
            bool hit = cache.TryGetValue(key, out node);
            hits.Add(hit);
            if (hit) {
                order.Remove(node);
                order.AddFirst(node);
            } else if (capacity > 0) {
                if (cache.Count == capacity) {
                    cache.Remove(order.Last.Value);
                    order.RemoveLast();
                }
                cache[key] = order.AddFirst(key);
            }
        }
        return new Dictionary < string, object > {
            {
                "hits", hits
            }, {
                "keys", new List < string >(order)
            }
        };
    }
}