[BOJ] 1700. 멀티탭 스케줄링

문제

---

OS 에서 스케쥴링할 때 Page Replacement 에서 Optimal 한 알고리즘과 동일하다.

포인트

---

현재 콘센트가 꽉차지 않았다면 채워주고 다음 사용 순서가 현재 콘센트에 존재하면 그대로 넘어간다. 문제는 콘센트가 꽉 차 있을 때 다음 사용 순서가 현재 콘센트에 존재하지 않아 하나를 제거할 때이다. 제거할 때 뒤에 사용 순서를 고려해 가장 가깝게 사용될 콘센트들은 그대로 냅두고 사용되지 않거나 가장 나중에 사용되는 콘센트를 제거한다. 이를 위해 현재 콘센트의 리스트를 복사하고 여기서 뒤쪽 사용 순서를 하나씩 돌아가면서 콘센트에서 제거하다가 가장 마지막에 남는 콘센트가 가장 나중에 사용되거나 사용되지 않는 것이므로 제거한다. 이때 사용되지 않는 콘센트가 두 개 이상일 수도 있으므로 cur_list[0] 을 임의로 제거한다!

난이도가 높은 문제를 풀고자하는데, 골드 1 치고 매우 쉬운 것 같다.

코드

---

n, k = map(int, input().split())

plugs = list(map(int, input().split()))

cur = []

cnt = 0
for i in range(k):
    if plugs[i] not in cur:
        if len(cur) >= n:
            cur_list = cur[:]
            for j in range(i + 1, k):
                if len(cur_list) == 1:
                    break
                if plugs[j] in cur_list:
                    cur_list.remove(plugs[j])
            cur.remove(cur_list[0])
            cur.append(plugs[i])
            cnt += 1
        else:
            cur.append(plugs[i])
print(cnt)