[Python] 백준 1700번 - 멀티탭 스케줄링

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

1700번: 멀티탭 스케줄링

Greedy 알고리즘을 이용해서 풀면 되는 문제다.

Edge case짜는게 약하다는걸 많이 느낀 문제였다.

 

내가 처음 짠 로직은 다음과 같다.

1. 일단 멀티탭 구멍 개수만큼 전자기기를 꽂는다
2. 다음 전자기기가 이미 꽂혀있는 경우, 그냥 넘어간다.
3. 다음 전자기기가 꽂혀있지 않은 경우, 무슨 전자기기를 뺄지 선택한다.   
     3-1. 꽂힌 전자기기 중 남은 전자기기에 없는 전자기기가 있으면 뺀다.   
     3-2. 꽂힌 전자기기가 모두 남은 전자기기에 있는 전자기기 인 경우, 바로 다음 숫자에 해당하는 전자기기를 뺀다.
4. 선택된 전자기기를 빼고, 다음 전자기기를 꽂는다.
5. 2-4 반복

결과적으로 3-2의 로직이 잘못됐었고, 2가지의 edge case를 빠뜨리고 있었다.

3-2의 로직은 "가장 나중에 쓰이는 전자기기를 뺀다"가 되어야 한다.

내가 빠뜨린 에지케이스는 "꽂아야 할 전자기기가 1개 남았고, 안꽂혀있는 경우"와 "1번 로직 수행 시 초반에 같은 값들이 을어올 수 있다"는 거였다.

 

해당부분을 수정한 코드는 다음과 같다.

from collections import deque

n, k = map(int, input().split())
elec_list = list(map(int, input().split()))
tab = []
answer = 0

# 초기 멀티탭 구멍 개수만큼 전자기기 꽂기
for elec in elec_list[:]:
    if len(tab) == n:
        break
    if elec not in tab:
        tab.append(elec)
        elec_list.remove(elec)

# popleft하기 위해 deque로 바꿔주기
elec_list = deque(elec_list)

while elec_list:
    # 다음 전자기기가 이미 꽂혀있는 경우, 그냥 넘어간다.
    if elec_list[0] in tab:
        elec_list.popleft()
    # 다음 전자기기가 꽂혀있지 않은 경우
    else:
        flag = 0
        # 꽂힌 전자기기 중 남은 전자기기에 없는 전자기기가 있으면
        for elec in tab:
            if elec not in elec_list:
                flag = 1
                tab.remove(elec)
                answer += 1
                tab.append(elec_list.popleft())
                break
        # 다음 전자기기가 1개 남은 경우
        if flag == 0 and len(elec_list) == 0:
            answer += 1
            del tab[0]
            tab.append(elec_list.popleft())
        # 꽂힌 전자기기가 모두 남은 전자기기에 있는 전자기기 인 경우
        elif flag == 0 and len(elec_list) != 1:
            idx = max([elec_list.index(i) for i in tab])
            tab.remove(elec_list[idx])
            answer += 1
            tab.append(elec_list.popleft())
                
print(answer)