キャッシュ(Programmers 17680)

🧑‍💻 キャッシュ

地図開発チームで働いているJazzieは、地図上で都市名を検索し、その都市に関連する美食店の投稿をデータベースで読み取るサービスを開発している.

このプログラムのテストを担当している人は、サービスを開く前に各ロジックのパフォーマンステストを行い、Jazzieが作成した部分でデータベースから投稿を取得した部分が実行時間が長すぎることを発見しました.

エピッチはJazzyにその論理改善を促し始め、JazzyはDBキャッシュを使用して性能を改善しようと試みたが、キャッシュサイズがどれだけ有効なのか分からず、Jazzyは気まずい思いをした.

言語のピークに悩まされているJazzyを支援し、DBキャッシュを適用する際に、キャッシュサイズに基づいて実行時間測定プログラムを作成します.

入力フォーマット

キャッシュ・サイズ(cacheSize)と都市名配列(cities)を入力します.

24172 cacheSizeは整数で、範囲は0≦cacheSize≦30です.

都市は都市名からなる文字列で並び、最大都市数は100000都市である.

各都市名は、スペース、数字、特殊文字を含まない英語文字からなり、大文字と小文字を区別しない.都市名は最大20文字で構成されています.

出力フォーマット

で入力された都市名の並びを順番に処理すると、「総運行時間」が出力される.

条件

キャッシュ置換アルゴリズムは、最新の使用(LRU)を使用する.

cacheヒットの場合、実行時間は1です.

cachemissの場合、実行時間は5です.

I/O例
cacheSizecitiesreturn3["Jeju", "Pangyo", "Seoul", "NewYork", "LA", "Jeju", "Pangyo", "Seoul", "NewYork", "LA"]503["Jeju", "Pangyo", "Seoul", "Jeju", "Pangyo", "Seoul", "Jeju", "Pangyo", "Seoul"]212["Jeju", "Pangyo", "Seoul", "NewYork", "LA", "SanFrancisco", "Seoul", "Rome", "Paris", "Jeju", "NewYork", "Rome"]605["Jeju", "Pangyo", "Seoul", "NewYork", "LA", "SanFrancisco", "Seoul", "Rome", "Paris", "Jeju", "NewYork", "Rome"]522["Jeju", "Pangyo", "NewYork", "newyork"]160["Jeju", "Pangyo", "Seoul", "NewYork", "LA"]25

📌 LRUアルゴリズムを使う！

📌 Cache hit:すでに存在する場合、cache miss:存在しない場合

🧑‍💻 解決策

cache hitの場合はcache missの場合とは逆です.

cache Sizeが0の場合、異常処理を行うだけで

を終了する.

🧑‍💻 コード#コード#

def solution(cacheSize, cities) :
   answer = 0
   cache = []

   if cacheSize == 0 :
       return len(cities) * 5

   for city in cities :
       city = city.lower()
       if not city in cache :
           if len(cache) < cacheSize :
               answer += 5
               cache.append(city)
           else :
               answer += 5
               cache.pop(0)
               cache.append(city)
       else :
           answer += 1
           cache.remove(city)
           cache.append(city)

   return answer

🧑‍💻 総評

これは簡単な問題です.

LRUアルゴリズムを学習すれば、すぐに適用することができる.