준호씨의 블로그

PS - 캐시(Cache) - 2018 KAKAO BLIND RECRUITMENT 1차 3번 본문

개발이야기/PS - Problem Solving, 알고리즘

PS - 캐시(Cache) - 2018 KAKAO BLIND RECRUITMENT 1차 3번

준호씨 2018. 9. 15. 00:25
반응형

https://gist.github.com/junho85/0d8c4beb0441bb0337914ca6e69dd915

과정

처음에는 fixed size list 를 사용할 방법을 찾아 보다가 deque 라는 녀석을 알게 되었다. (https://stackoverflow.com/a/16430458/964890) 새로운 값이 들어가면 자연스럽게 기존에 들어갔던 값이 제거 되니 딱 적절해 보였다.

처음에는 이렇게 짰는데 첫번째 테스트를 무사히 통과 했다.

def solution(cacheSize, cities):
    answer = 0

    q = deque(maxlen=cacheSize)

    for item in cities:
        if item in q:
            answer += 1
        else:
            answer += 5
            q.append(item)

    return answer

그런데 대소문자 구분을 하지 말아야 된다는 조건 때문에 5번째 테스트에서 실패 하였다.

대소문자 구분을 하지 않도록 하려면 보통 소문자로 통일하거나 대문자로 통일하면 된다. 다음과 같이 소문자로 통일 시켰다.

    for item in cities:
        item = item.lower()

기본 테스트 6개는 통과 했는데 제출 하니 실패하였다.

문제를 다시 보니 캐시 교체 알고리즘으로 LRU (Least Recently Used) 를 사용하라고 적혀 있었다. 최근에 사용했던 녀석을 살리는 방식이다.

그냥 다음과 같이 기존에 존재하던 값이면 뺐다가 다시 집어 넣어 주도록 해 주었다.

        if item in q:
            answer += 1
            q.remove(item)
            q.append(item)

이러면 자연스럽게 최근에 사용된 녀석이 큐의 마지막에 들어가게 되어서 사용하지 않은 녀석들은 점점 밀려 나가서 사라지는 LRU 방식을 적용 할 수 있게 된다.

python 의 유용한 기법

in for list

list 에 존재하는 지 여부는 in 으로 쉽게 구현 가능하다.

somelist = [1,2,3]

일때

if 1 in somelist:

는 True 이고

if 9 in somelist:

는 False 이다.

deque

https://docs.python.org/3.7/library/collections.html#collections.deque

참고

반응형

'개발이야기 > PS - Problem Solving, 알고리즘' 카테고리의 다른 글

LeetCode 1. Two Sum C++ 풀이  (2) 2018.10.25
PS - 비밀지도 javascript  (0) 2018.10.17
PS - 다트게임 - 2018 KAKAO BLIND RECRUITMENT 1차 2번  (0) 2018.09.14
PS - 비밀지도 - 2018 KAKAO BLIND RECRUITMENT 1차 1번 문제  (0) 2018.09.13
python - 문제 풀이 할 때 알아 두면 유용한 loop 기법  (0) 2018.09.12
공유하기 링크
'개발이야기/PS - Problem Solving, 알고리즘' Related Articles more
Comments