[BOJ][Python] 백준 1881 번: 공 바꾸기

1일 1PS 67일차!

📚 문제

---

골드 2 공 바꾸기

💡 풀이 과정

---

• 문제를 읽으면 페이징 교체 알고리즘의 최적 교체 알고리즘을 구현하라는 것을 쉽게 알 수 있습니다.
• 페이징 교체 시 뒤 쪽을 바라보며 바로 뒤에 사용되는 페이지들을 우선적으로 남겨놓는 방법입니다.
  • 실제로는 뒤에 어떤 프로세스가 올 지 모르기에 사용할 수 없지만 해당 문제에서는 모든 공의 순서를 이미 나타내고 있어 사용할 수 있습니다.
• 우선 해당 공이 존재하는 지 확인하고, 상자가 남는 지 확인합니다.
  • 이후 교체해야한다면 뒤쪽 순번을 가까운 순서대로 확인해 우선적으로 남겨야할 것을 체크합니다.
  • 이후에 우선순위가 가장 낮은 볼을 교환합니다.

📌포인트

---

• 삽입연산
  • 삽입 시에도 연산이 진행되므로 문제 조건 상 operation 을 +1 해줘야합니다.
• EOFError
  • 해당 문제에서는 n 의 입력값이 0 이 아님을 보장하지 않습니다.
  • 따라서 0 일때는 input 을 받게되면 EOF Error 가 발생하기 때문에 조건문을 작성해야합니다.

💻 코드

---

import copy


def optimal_page_replacement(cards):
    memory_frames = []
    operations = 0

    for i in range(len(cards)):
        if cards[i] in memory_frames:
            continue
        else:
            if len(memory_frames) < 4:
                memory_frames.append(cards[i])
                operations += 1
            else:
                temp = copy.deepcopy(memory_frames)
                for j in range(i + 1, len(cards)):
                    if len(temp) != 1:
                        if cards[j] in temp:
                            temp.remove(cards[j])
                    else:
                        break
                memory_frames.remove(temp[0])
                memory_frames.append(cards[i])
                operations += 1


    return operations

n = int(input())
if n == 0:
    print(0)
else:
    cards = list(map(int, input().split()))

    result = optimal_page_replacement(cards)
    print(result)