[백준 1700번] 파이썬 - 멀티탭 스케줄링

http://www.acmicpc.net/problem/1700

1700번: 멀티탭 스케줄링

 

 

# 조건

• 기숙사에서 살고 있는 준규는 한 개의 멀티탭을 이용하고 있다.
• 준규는 키보드, 헤어드라이기, 핸드폰 충전기, 디지털 카메라 충전기 등 여러 개의 전기용품을 사용하면서 어쩔 수 없이 각종 전기용품의 플러그를 뺐다 꽂았다 하는 불편함을 겪고 있다.
• 그래서 준규는 자신의 생활 패턴을 분석하여, 자기가 사용하고 있는 전기용품의 사용순서를 알아내었고, 이를 기반으로 플러그를 빼는 횟수를 최소화하는 방법을 고안하여 보다 쾌적한 생활환경을 만들려고 한다.
• 예를 들어 3 구(구멍이 세 개 달린) 멀티탭을 쓸 때, 전기용품의 사용 순서가 아래와 같이 주어진다면,
  1. 키보드
  2. 헤어드라이기
  3. 핸드폰 충전기
  4. 디지털 카메라 충전기
  5. 키보드
  6. 헤어드라이기
• 키보드, 헤어드라이기, 핸드폰 충전기의 플러그를 순서대로 멀티탭에 꽂은 다음 디지털 카메라 충전기 플러그를 꽂기 전에 핸드폰충전기 플러그를 빼는 것이 최적일 것이므로 플러그는 한 번만 빼면 된다.

 

입력

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

 

# 접근 방법

• 문제 이해부터 조금 어려웠다.
• 사용 빈도가 아닌 사용 순서로 물품을 구분해놨다.
• 우선 -> 멀티탭에 서로 다른 물건이 꽂히는 동안 using 리스트에 넣어주며 인덱스 번호 기록
• 이후 idx 부터 시작하여 교체 시작
• 멀티탭에 없는 경우 ->
  • 남아있는 물건들을 체크해주는데
  • using 리스트를 change 리스트에 깊은 복사해주며, 길이가 1이하인 경우 까지 아래 반복
    • 먼저 쓰이는 물건이 change 리스트에 존재하면 remove 해준다.
    • 마지막까지 꽂혀있는 번호 -> 가장 늦게 사용되거나 사용하지 않는 물건
  • 이후 원본 using 리스트에서 change의 0번 인덱스 물건을 remove 해주고 현재 인덱스의 물건 꼽아주기

 

 

-> 가상 메모리의 스케줄링 이론 중 하나인 Optimal Algorithm을 구현해보는 문제
가까운 미래에 쓰이는 것을 놔두고, 가장 먼 미래에 쓰이는 것을 교체해야 한다.

 

import sys
sys.stdin = open('input.txt')
input = sys.stdin.readline

N, K = map(int, input().split())
use = [*map(int, input().split())]

# 멀티탭에 꽂혀있는 물건 번호
using = []
# 콘센트 뽑은 횟수
cnt = 0
# 현재 사용중인 물건 인덱스
idx = 0


# 먼저 멀티탭 채워주기
for i in use:
    # 이미 멀티탭에 꽂혀있다면 패스
    if i in using:
        idx+=1
        continue
    # 멀티 탭에 빈 자리가 있다면
    if not len(using) == N:
        idx+=1
        using.append(i)
    # 멀티 탭이 꽉 찼다면 종료 후 교체 시작
    else:
        break

for j in range(idx, K):
    if use[j] not in using:
        # 남아있는 물건들
        change = using[:]
        for k in range(j+1, K):
            # 가장 마지막에 사용되는 물건 찾아주기
            # 길이가 1이하이면 우선 사용되는 물건들이 리스트에서 지워져있다.
            if len(change) <= 1:
                break
            # 현재 콘센트에 꽂혀 있다면
            # 제거해준다.
            elif use[k] in change:
                change.remove(use[k])
        # change 리스트에 남아있는 물건이 가장 늦게 사용됨
        # 제거 후 추가 해주기
        using.remove(change[0])
        using.append(use[j])
        cnt+=1

print(cnt)