[프로그래머스] 캐시

내 코드

def solution(cacheSize, cities):
    answer = 0
    
    q = []
    
    cities = [i.lower() for i in cities]
    
    if cacheSize==0:
        return len(cities)*5

    for city in cities:
        if city in q:
            answer+=1
            q.remove(city)
            q.append(city)
        else:
            answer+=5
            if len(q) == cacheSize:
                q.pop(0)
            q.append(city)
        
    return answer

LRU 알고리즘은 페이지 교체 알고리즘 중에 하나로 가장 오랫동안 참조되지 않은 페이지를 교체하는 기법이다. 운영체제 시간에 배웠었는데.. 오랜만에 본다. 이런식으로 문제도 적용될 수 있는걸 처음알았다 ㅎ

 

q에서 지금 참조되고 있는 페이지를 관리할 것이다. 가장 오랫동안 참조되지 않은 페이지를 찾아야하므로 q에 최근에 참조된 페이지들을 append해서 풀것이다. 그럼 제일 첫번째로 있는 원소가 (q[0])이 가장 오랫동안 참조되지 않은 페이지이다.

 

대문자 소문자를 구분하지 않기 때문에 lower을 사용해서 소문자로 다 바꿔주었다.

캐시 사이즈가 0이면 전부 miss이기 때문에 시티 길이만큼 5를 곱해준다.

 

시티를 for문으로 돌면서 구해줄껀데 시티가 q에 있으면 페이지가 있는 것이기 때문에 1을 더해준다. 사용한 페이지는 q의 가장 뒤로 보내야하기때문에 q에서 제거하고 append로 다시 추가해준다.

만약 q에 없으면 추가해야하는데 q의 길이가 캐시사이즈와 같으면 제일 앞 페이지를 제거해준다.

---

다른사람 코드

def solution(cacheSize, cities):
    import collections
    cache = collections.deque(maxlen=cacheSize)
    time = 0
    for i in cities:
        s = i.lower()
        if s in cache:
            cache.remove(s)
            cache.append(s)
            time += 1
        else:
            cache.append(s)
            time += 5
    return time

deque 저번에 정리했었는데 ,, maxlen은 처음본다. 

deque를 maxlen을 지정해주면 길이가 길어지면 deque의 최대길이를 n으로 제한한다. 오른쪽으로 값이 추가되면 왼쪽에서 부터 값이 삭제된다. 이렇게 deque로 지정해주어서 len의 값을 비교할 작업이 사라졌다.

나는 먼저 소문자로 다 바꾸고 했는데 이렇게 시티를 빼면서 소문자로 하는게 더 빠른것같다.

나머지는 나와같음!