문제 링크

문제

기숙사에서 살고 있는 준규는 한 개의 멀티탭을 이용하고 있다. 준규는 키보드, 헤어드라이기, 핸드폰 충전기, 디지털 카메라 충전기 등 여러 개의 전기용품을 사용하면서 어쩔 수 없이 각종 전기용품의 플러그를 뺐다 꽂았다 하는 불편함을 겪고 있다. 그래서 준규는 자신의 생활 패턴을 분석하여, 자기가 사용하고 있는 전기용품의 사용순서를 알아내었고, 이를 기반으로 플러그를 빼는 횟수를 최소화하는 방법을 고안하여 보다 쾌적한 생활환경을 만들려고 한다.

예를 들어 3 구(구멍이 세 개 달린) 멀티탭을 쓸 때, 전기용품의 사용 순서가 아래와 같이 주어진다면,

키보드
헤어드라이기
핸드폰 충전기
디지털 카메라 충전기
키보드
헤어드라이기
키보드, 헤어드라이기, 핸드폰 충전기의 플러그를 순서대로 멀티탭에 꽂은 다음 디지털 카메라 충전기 플러그를 꽂기 전에 핸드폰충전기 플러그를 빼는 것이 최적일 것이므로 플러그는 한 번만 빼면 된다.

입력

첫 줄에는 멀티탭 구멍의 개수 N (1 ≤ N ≤ 100)과 전기 용품의 총 사용횟수 K (1 ≤ K ≤ 100)가 정수로 주어진다. 두 번째 줄에는 전기용품의 이름이 K 이하의 자연수로 사용 순서대로 주어진다. 각 줄의 모든 정수 사이는 공백문자로 구분되어 있다.

출력

하나씩 플러그를 빼는 최소의 횟수를 출력하시오.

풀이

문제를 보자마자 페이지 교체 알고리즘이 떠올랐다.
어떤 전기용품을 이용할 것인지 전부 입력으로 주어지므로, Optimal 페이지 교체 알고리즘을 사용해야 하는 것으로 보인다.
optimal 교체 알고리즘의 경우 찾아보니 LFD, 벨라디 min 알고리즘 이라고도 하는 것 같다.

먼저 전기용품들이 언제 이용하는 지 시간을 저장하고, 현재 꽂힌 전기용품을 리스트에 넣은 후 가장 나중에 오는 전기용품을 교체하도록 하면 어떤가 라는 방안을 생각해보았다.

예제를 통해 확인해 보았다.

2 5
1 2 3 1 2

다음과 같은 입력이 주어졌을 때, 전기용품 3에 대해 플러그에 꽂힌 전기용품 1을 교체하면 바로 다음에 전기용품 1로 다시 교체해야 하므로 전기용품 2를 교체해야 한다.

2 8
1 2 3 4 5 6 7 1

다음과 같은 입력이 들어올 시, 추후 사용할 여지가 가장 높은 것을 남기는 것이 가장 적절할 것이라 생각했다.

논리가 많이 빈약한데, 정보처리기사에서도 나온 개념이기도 하니 나보단 책을 믿는다는 느낌으로 구현해보았다...
처음 제출했을 때는 키 에러가 나왔었는데, 플러그에 더 꽂을 수 있을 때 전자제품을 중복으로 꽂아 에러가 발생했었다.

input = open(0).readline
# page fault optimal algorithm...?
N, K = map(int, input().split())
plug = [*map(int, input().split())]

future = dict() # 미래시

for i in range(K-1, -1, -1):
    if plug[i] in future: future[plug[i]].append(i)
    else: future[plug[i]] = [-1, i]

memory = []
m_set = set() # 중복 무시 빠른 찾기
length = 0 # 메모리 현재 길이
cnt = 0
for i in range(K):
    current = plug[i]
    if length < N:
        # 안쓰고 있고 자리 남아있으면 집어넣음
        if current not in m_set:
            memory.append(current)
            m_set.add(current)
            length += 1
        future[current].pop()
    else:
        # print(m_set, memory)
        # 있으면 생략
        if current in m_set:
            future[current].pop()
            continue
        change = 0
        latest_position = i
        for j in range(N):
            if future[memory[j]][-1] == -1: # 더이상 나오지 않을 때
                latest_position = future[memory[j]][-1]
                change = j
                break
            elif future[memory[j]][-1] > latest_position: # 현재 가장 늦는 것
                latest_position = future[memory[j]][-1]
                change = j
            # print(change, future[memory[j]], i)
        # 메모리 집합 갱신
        m_set.remove(memory[change])
        m_set.add(plug[i])
        # page fault 교체
        memory[change] = plug[i]
        future[memory[change]].pop()
        cnt += 1
    # print(memory)
        
print(cnt)

코드가 길어서 클래스로 만들까도 생각했었는데, 다른 풀이의 경우 굳이 그렇게 하지 않고 빠르게 풀었다.
교체할 전자용품을 찾을 때 우선순위 큐를 이용하는 법도 생각해 볼 수 있을 것 같다.