2018 KAKAO BLIND RECRUITMENT 캐시 파이썬

2018 KAKAO BLIND RECRUITMENT 캐시 파이썬 풀이

바로 이전에 풀었던 수식 최대화와 동일한 2레벨 문제입니다.

LRU 알고리즘을 처음 접해서 기본적인 개념에 대해서 공부했습니다.

유용했던 자료는 아래에 링크를 첨부해두었습니다.

• 코드없는 프로그래밍 - 코딩 테스트, 중급, LRU cache
• 예비개발자의 일상 - LRU 알고리즘 (Least Recentely Used) 개념 및 구현방법

LRU 알고리즘

배운 것을 토대로 LRU 알고리즘에 대해서 설명하자면,
LRU 알고리즘은 연결리스트에서 해당 리스트의 max_size를 초과하여 입력값이 주어졌을 때,
가장 오랫동안 사용되지 않은 원소를 제거하고 남은 자리에 새로운 입력값을 대체해주는 알고리즘입니다.
즉, max_size가 3이라고 가정할 때, 처음 3개의 원소까지는 문제없이 저장되지만, 그 이후부터 연결리스트에
존재하지 않는 원소가 입력값으로 주어질 경우, 기존에 저장된 원소들 중 가장 사용되지 않은 원소가 삭제됩니다.
그러면 size가 1 남게 되고, 그 자리를 대체하게 되는 것입니다.

정답코드

해당 코드는 Gemma.log님의 풀이에서 가져온 것입니다.

접근 방식

1. cache라는 리스트에 주어진 입력값들을 넣어줍니다.
2. 우선 lower()함수를 이용해서 입력값을 공통적으로 소문자로 만들어줍니다.
3. cacheSize가 0일 경우 어떠한 입력값도 저장되지 않기 때문에 time에 5를 계속 더해줍니다.
4. 만약 입력값이 리스트에 들어있지 않을 경우엔 리스트에 append 시켜줍니다.
5. 하지만 리스트에 들어있지 않고, 이미 리스트의 크기가 max_size일 경우, 가장 처음 들어간 원소를 pop해줍니다.
6. 그 후 마지막에 입력값을 append 시켜줍니다.
7. 핵심은 만약 입력값이 리스트에 들어있을 경우, 이를 참조했다는 것을 나타내기 위해 해당 값을 삭제하고, 리스트의 마지막에 다시 append 시켜줘야합니다. 이런 rewiring이 필요합니다.

def solution(cacheSize, cities):
    cache = []
    time = 0
    for city in cities:
        city = city.lower()
        if cacheSize:
            if not city in cache:
                if len(cache) == cacheSize:
                    cache.pop(0)
                cache.append(city)
                time += 5
                # rewiring 부분
                # 참조했기 때문에 해당 입력값을 가장 마지막 원소로 재배치 해줍니다.
            else:
                cache.pop(cache.index(city))
                cache.append(city)
                time += 1
        # cacheSize == 0
        else:
            time += 5
    return time

이번 문제를 풀면서 LRU 알고리즘의 개념과 구현 방법에 대해서 배울 수 있었습니다.

가장 중요했던 부분은 rewiring 작업을 pop과 append를 연속적으로 사용해서 재배치해주는 부분이라고 생각합니다.

pop과 append 연산을 활용하여 stack 자료구조의 원리로 LRU알고리즘을 구현할 수 있었고,

알고리즘 문제를 풀면서, 이러한 특정 알고리즘의 원리를 알고 있지 않다면 풀이를 할 수 없다는 것을 배웠고,

다양한 알고리즘을 접하는 것의 중요성을 배웠습니다.

알고리즘도 모든 것과 마찬가지로 꾸준한 연습과 이해를 바탕으로 실력이 향상합니다.
Just do it & Keep steady