<aside> 💬 lv0, 데이터 구조

최근 사용된 페이지 관리

문제 설명

사용자가 방문한 웹 페이지의 기록을 순서대로 유지하는 목록을 구현해주세요. 목록의 크기는 제한되어 있으며, 새로운 페이지가 추가될 때 목록이 가득 찬 경우 가장 오래된 페이지를 제거해야 합니다. 이미 목록에 존재하는 페이지를 다시 방문하는 경우, 해당 페이지는 목록의 가장 뒤로 이동해야 합니다.

예를 들어, 목록의 크기가 3이고, 순서대로 page1, page2, page3, page2, page4 페이지가 방문되었다면, 최종적으로 목록에는 [page3, page2, page4]가 남게 됩니다.

제한 사항

• 목록의 크기는 1 이상 100 이하의 정수로 주어집니다.
• 페이지는 문자열로 표현되며, 최대 100개의 페이지가 주어질 수 있습니다.

입출력 예

입출력 설명

사용자가 방문한 페이지의 기록을 크기 제한에 따라 관리합니다. 페이지가 다시 방문되면 기존 순서를 갱신합니다.

</aside>

😺 풀이 1. OrderedDict 활용

from collections import OrderedDict

def solution(data):
    size = data["size"] **#1 입력 데이터 처리**
    pages = data["pages"]
    cache = OrderedDict() **#2 OrderedDict 초기화**

    for page in pages: **#3 페이지 방문 처리**
        if page in cache:
            cache.pop(page)
        elif len(cache) >= size:
            cache.popitem(last=False)
        cache[page] = True
    return list(cache.keys()) **#4 최종 목록 반환**

단계별 풀이 전략

1. 입력 데이터 처리

   data 딕셔너리에서 size (목록의 최대 크기)와 pages (방문한 페이지 목록)를 추출합니다.

2. OrderedDict 초기화

   OrderedDict를 사용하여 순서가 유지되는 캐시(cache)를 초기화합니다. OrderedDict는 요소가 추가된 순서대로 요소를 저장합니다.

3. 페이지 방문 처리

   1. 각 페이지에 대해 순회를 시작합니다.
   2. 이미 캐시에 존재하는 페이지를 다시 방문하는 경우, 해당 페이지를 캐시에서 제거한 후 캐시의 맨 뒤로 다시 추가합니다. 이렇게 하면 페이지가 최근에 방문되었음을 반영합니다.
   3. 캐시의 크기가 목록의 최대 크기(size)에 도달한 경우, 가장 오래된 페이지를 제거하고, 새 페이지를 캐시의 맨 뒤에 추가합니다.

4. 최종 목록 반환

   처리가 완료된 캐시에서 키(페이지) 목록을 추출하여 리스트로 반환합니다.

알아둬야 할 개념

OrderedDict 자료구조

• 기본 형태: from collections import OrderedDict

• 개념: Python의 collections 모듈에 있는 OrderedDict는 요소가 추가된 순서대로 요소를 저장하는 딕셔너리형 자료구조입니다. 이를 통해 삽입 순서가 중요한 경우에 유용하게 사용할 수 있습니다.

  from collections import OrderedDict
  
  ordered_dict = OrderedDict() #OrderedDict 생성
  ordered_dict['banana'] = 3 #OrderedDict 추가
  ordered_dict['apple'] = 4
  ordered_dict['pear'] = 1
  
  for key, value in ordered_dict.items(): #추가된 순서대로 출력
      print(key, value)
  

풀이 2. Deque

def solution(data):
    size = data['size'] **#1 입력 데이터 처리**
    pages = data['pages']

    return pages[-(size):] **#2 최신 페이지만 유지**

단계별 풀이 전략

1. 입력 데이터 처리

   입력으로 주어진 data에서 size (목록의 크기)와 pages (방문한 페이지 목록)를 추출합니다. 이 단계에서는 문제의 설정에 따라 필요한 초기 데이터를 준비합니다.

2. 최신 페이지만 유지

   제공된 코드는 목록의 크기를 고려하여 최신 size 개수의 페이지만을 반환합니다. 이는 pages[-(size):]를 통해 구현됩니다. 하지만, 이 방법은 이미 방문한 페이지를 다시 방문했을 때의 처리와 목록이 가득 찬 경우 오래된 페이지를 제거합니다.

알아둬야 할 개념

Deque (데큐)