[2018 Kakao Blind Recruitment 1차] Q3. 캐시(C++, Python, JAVA)

programmers.co.kr/learn/courses/30/lessons/17680

 

알고리즘 분류

Implementation

 

풀이

캐시를 리스트 안에서 등장한 순으로 둡니다. 예전에 등장한 도시가 앞에, 최근에 등장한 도시가 뒤에 위치하도록 했습니다.(반대여도 상관없습니다.)

 

대소문자 구분이 없다고 명시되어있기 때문에 미리 도시 이름을 소문자로 만드는 처리를 해둡니다. 도시의 이름을 하나씩 살펴보면서 리스트 안에 해당 도시가 존재하는지 아닌지를 우선 판단합니다. 도시가 캐시 리스트 안에 있다면 해당 도시를 리스트에서 가장 뒤로 보냅니다. 캐시 리스트 안에 없다면 해당 도시를 리스트의 뒤에 추가하는데 캐시 크기가 cacheSize를 넘어섰다면 리스트에서 제일 앞의 도시를 지웁니다.

 

도시의 개수를 N, cacheSize를 M이라고 할 때 각 도시에 대해 캐시 리스트 전부를 살펴보는 작업이 필요하기 때문에 O(NM)입니다.

 

코드(C++)

#include <bits/stdc++.h>
using namespace std;

string lower(string& s){
    string ret;
    for(char c : s) ret += tolower(c);
    return ret;
}

int solution(int cacheSize, vector<string> cities) {
    vector<string> cache;
    int ret = 0;
    for(string& city : cities){
        // 소문자로 변환한 이름
        string lo = lower(city); 
        auto it = find(cache.begin(), cache.end(), lo);
        if(it == cache.end()){
            ret += 5;
            cache.push_back(lo);
            if(cache.size() > cacheSize)
                cache.erase(cache.begin());
        }
        else{
            ret += 1;
            cache.erase(it);
            cache.push_back(lo);
        }
    }
    return ret;
}

 

캐시 리스트에서 원소를 찾고, 원소를 지우거나 추가하는 것을 string 배열에서 수행해도 되지만 vector를 이용하면 더 간단하게 처리할 수 있습니다.

 

캐시 리스트 안에 lo가 있다면 cache에서 lo를 지우고 뒤에 삽입함으로서 lo를 제일 뒤로 보내고, lo가 없다면 일단 lo를 추가한 뒤 캐시 리스트의 크기가 cacheSize보다 클 경우 제일 앞의 도시를 제거했습니다.

 

코드(Python)

def solution(cacheSize, cities):
    cache = []
    ret = 0
    for city in cities:
        lo = city.lower()
        try:
            # lo가 없을 경우 여기서 exception 발생
            idx = cache.index(lo)
            ret += 1
            cache.pop(idx)
            cache.append(lo)
        except:
            ret += 5
            cache.append(lo)
            if len(cache) > cacheSize:
                cache.pop(0)
    return ret

파이썬 list의 index 메소드를 이용해 cache 내에 lo가 존재하는지를 확인했습니다.

 

캐시 리스트 안에 lo가 있다면 cache에서 lo를 지우고 뒤에 삽입함으로서 lo를 제일 뒤로 보내고, lo가 없다면 일단 lo를 추가한 뒤 캐시 리스트의 크기가 cacheSize보다 클 경우 제일 앞의 도시를 제거했습니다.

 

코드(JAVA)

import java.util.*;

class Solution {
    public int solution(int cacheSize, String[] cities) {
        int ret = 0;
        ArrayList cache = new ArrayList();
        for(int i = 0; i < cities.length; i++){
            String lo = cities[i].toLowerCase();
            // true일 경우 삭제에 성공(cache hit)
            if(cache.remove(lo)){
                ret += 1;
                cache.add(lo);
            }
            else{
                ret += 5;
                cache.add(lo);
                if(cache.size() > cacheSize)
                    cache.remove(0);
            }
        }
        return ret;
    }
}

자바 ArrayList의 remove 메소드는 삭제에 성공했는지 여부를 알려준다는 점을 이용해 코드를 구성했습니다.

 

캐시 리스트 안에 lo가 있다면 cache에서 lo를 지우고 뒤에 삽입함으로서 lo를 제일 뒤로 보내고, lo가 없다면 일단 lo를 추가한 뒤 캐시 리스트의 크기가 cacheSize보다 클 경우 제일 앞의 도시를 제거했습니다.