백준 1700: 멀티탭 스케줄링 - 그리디

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

1700번: 멀티탭 스케줄링

사용할 전기용품을 플러그에 꽂기 전에 세 가지 경우를 생각해야합니다.

1. 이미 꽂혀 있는 경우
2. 멀티탭에 빈 공간이 있는 경우
3. 멀티탭에 있는 것을 뽑고, 새로운 것을 꽂아야 할 경우

1번의 경우 그냥 넘어가주면되고, 2번의 경우는 꽂고 넘어가주면 됩니다.

 

3번의 경우는 제일 마지막에 사용되거나, 앞으로 사용하는 일이 없는 것을 찾아 바꿔줍니다.

플러그에 꽂힌 전기용품을 기준으로 for문을 돌면서 현재 사용중인 전기용품이 다음에 언제 나오는 지 index를 count해주고 maximum_count와 to_switch에 적용해줍니다. (새로 꽂으려고 하는 전기용품 이후에 몇 번 오는 지)

maximum_count는 제일 마지막에 사용되는 전기용품이 몇 번째에 사용되는 지 count해준 것이고(사용되지 않을 때 제일 큰 값) 이는 for문을 돌면서 더 뒤에 사용되는 것이 생길 때마다 갱신됩니다.

to_switch는 maximum_count에 해당하는 전기용품을 뽑기 위해 사용되는 변수입니다.

 

 

전기용품이 사용중인 지 확인할 때마다 전체 멀티탭을 돌고 싶지 않아서 'current_on' 변수로 현재 꽂혀있는 전기용품에 True 값을 넣어주었습니다.

따라서 새로 꽂을 떄는 current_on[전기용품 인덱스] = True로 해주고, 뺄 때는 False로 변경해주어야 합니다.

 

 

from sys import stdin
input = stdin.readline

multitap_num, schedule_num = map(int, input().split())

result = 0
schedule = list(map(int, input().split()))
multitap = []
current_on = [False for _ in range(schedule_num+1)] #schedule_num 이하의 자연수만 입력됨
for ii, ss in enumerate(schedule):
    # 이미 꽂혀 있을 때
    if current_on[ss]:
        continue
    # 빈 공간이 있을 때
    if len(multitap) < multitap_num:
        multitap.append(ss)
        current_on[ss] = True
        continue
    
    # 바꿔줘야 할 때
    maximum_count = -1
    to_switch = 0
    for mm in range(multitap_num):
        current_count = 0
        for tmp in range(ii+1, schedule_num):
            if multitap[mm] == schedule[tmp]:
                break
            current_count += 1
        if current_count > maximum_count:
            maximum_count = current_count
            to_switch = mm
    
    current_on[multitap[to_switch]] = False
    multitap[to_switch] = ss
    current_on[ss] = True
    result += 1

print(result)