[BOJ] Q1700 멀티탭 스케쥴링

[BOJ] Q1700 멀티탭 스케쥴링

Question

Language: Python

Difficulty: Gold 1

멀티탭에 장비를 꽂아 사용하는데, 멀티탭이 다 꽂혀있을 경우, 특정 장비를 하나 제거해서 그 자리에 꽂아서 사용할 수 있다. 이때 이와 같이, 장비를 교체하는(플러그를 빼는) 횟수를 최소화 해야한다.

만약 이미 멀티탭에 꽂혀있는 장비에 대해 장비를 사용하고자 한다면 플러그를 뺄 필요가 없다 만약 멀티탭에 자리가 있으면 빈 자리에 장비를 꽂으면 된다. 만약 멀티탭에 자리가 없으면 특정 장비 하나를 제거해서 그 자리에 장비를 꽂아야한다.

이는 Process Scheduling 과 연관된 문제이다 플러그를 빼는 횟수를 최소화 하기 위해서는 꽂혀 있는 나중에 장비가 사용되는 시점이 가장 늦은 장비를 골라서 교체해야한다.

input 조건을 보면 장비가 최대 100번 이용될 수 있다. 따라서, 매번 모든 장비가 언제 사용되는 지 알아보기 위해 전체 탐색을 진행해도 해결할 수 있다.

Solution

def solution(N,k,tasks):
  operators=[]

  unplug_count=0
  
  while tasks:
    task=tasks.pop(0)
    if task in operators:
        continue
    elif len(operators) < N:
      operators.append(task)
    else:
      #모든 작업에 대해 미래에 호출되는 시점을 파악하기 위한 리스트
      future_access=[0]*N
      
      for index, operator in enumerate(operators):
        #만약 장비가 미래에 사용될 일이 있으면 해당 시간이 언제인지 파악한다.
        if operator in tasks:
          future_access[index]=tasks.index(operator)
        else:
          #101는 더 이상 장비가 사용될 일이 없음을 의미한다.
          future_access[index]=101
          
      index=future_access.index(max(future_access))
      del operators[index]
      operators.append(task)
      #장비를 제거하고 새로운 장비를 멀티탭에 등록
      unplug_count+=1
        
      
  return unplug_count
  
if __name__ == "__main__":
  N,k=0,0
  tasks=[]

  with open("input1700.txt","r") as file:
    N,k=map(int,file.readline().split())
    tasks=list(map(int,file.readline().split()))

  print(solution(N,k,tasks))