LV2 [KAKAO] [1차] 캐시

---

문제

https://school.programmers.co.kr/learn/courses/30/lessons/17680#

프로그래머스

풀이

해당 문제는 그냥 LRU 알고리즘 동작 방식을 공부하고 구현하면 된다. LRU를 몰랐다면 못풀었을 거 같은..

 

아무튼, LRU는 연결리스트로 구성되어 있기에 노드 클래스를 만들고, 연결리스트 클래스를 만들면 된다.

 

그리고 연결리스트 가장 앞에 넣는 (최근에 참조되었거나 새로 들어올 경우) 로직을 하나 만들고,

 

연결리스트를 cacheSize만큼 참조한 다음 매개변수로 들어온 data가 연결리스트에 있는지 판단하는 함수를 하나 만들었다. (나는 cacheSize를 넘어간다고 노드를 굳이 삭제하진 않았다. 물론 실제 프로그램이라면 메모리를 해제해줘야겠으나, 여기서는 그냥 cacheSize만큼 순회한다음 그게 넘어가면 없다고 판단했다.)

 

그리고 판단하는 함수에서 만약 데이터가 있다면 연결리스트의 가장 앞으로 위치시켜야하기 때문에 그 로직을 추가로 작성했다. ( 중간에 발견했을 경우 그 뒤의 노드와 앞의 노드를 이어주기 위해 before라는 포인터를 하나 더 설정했다. 단 찾는 데이터가 이미 가장 앞에 있을 경우에는,  로직 그대로 사용하면 가장 앞의 노드를 반복적으로 참조하기 때문에 바로 return 해주었다.)

 

만약 없을경우에는 가장 앞에 데이터를 넣어주면 된다.

 

코드

class Node:
    def __init__(self, data):
        self.data = data
        self.next = None

class LinkedList:
    def __init__(self):
        self.head = None

    def insertFirst(self, data):
        new_node = Node(data)
        new_node.next = self.head
        self.head = new_node

    def isExist(self, data, cacheSize):
        cur = self.head
        before = self.head
        idx = 1
        while cur and idx <= cacheSize:
            # 데이터를 찾았다면 해당 노드를 가장 앞으로 이동시켜준다.
            if cur.data == data:
                if idx == 1 : return True
                before.next = cur.next
                cur.next = self.head
                self.head = cur
                return True
            # 계속 탐색
            else:
                before = cur
                cur = cur.next
                idx += 1

        # 만약에 cacheSize를 넘어가거나, 리스트에 없다면 앞에 추가해준다.
        self.insertFirst(data)
        return False

def solution(cacheSize, cities):
    
    # LRU => 캐시 용량이 다 찼을때, 가장 오랫동안 사용하지 않은 친구를 교체한다. 
    lss = LinkedList()
    answer = 0
    
    for city in cities:
        # 모두 소문자로 바꿔준다.
        if lss.isExist(city.lower(), cacheSize):
            answer += 1
        else:
            answer += 5
    return answer

 

후기

 

이런 문제는 검색 안되면 답도 없겠다 싶었다. 배열로 어찌저찌 구현했으면 시간초과 100프로였겠지.. 

 

연결리스트 문제는 잘 안나오니 완전 잊고 있었는데 범주안에 둘 필요가 있겠다.