[BOJ/백준] 1700. 멀티탭 스케줄링 (Python)

🔎 문제

🔗 백준 1700번 멀티탭 스케줄링

💡 풀이

문제 지문에,

디지털 카메라 충전기 플러그를 꽂기 전에 핸드폰충전기 플러그를 빼는 것이 최적일 것이므로 플러그는 한 번만 빼면 된다.

이런 말이 있다. 핸드폰 충전기 플러그를 빼는 것이 최적인 이유는 핸드폰 충전기 플러그는 그 뒷 순서에 없으므로 뽑으면 다시 꽂을 일이 없기 때문이다(다시 꽂고 다시 뽑아야 할 일도 없다.)

따라서 플러그를 뽑아야 할 상황에서 1순위로는 뒷 순서에 등장하지 않는것을 뽑고, 만약 멀티탭에 꽂혀있는 모든 플러그가 뒷 순서에 등장한다면 가장 늦게 등장하는 플러그를 뽑는것이 최선일 것이다. 늦게 등장할 수록 뽑고 나서 오랫동안 다시 안꽂아도 되니까 뽑을 확률도 줄어든다.

플러그를 뽑지 않아도 될 상황은 꽂아야 할 제품이 이미 꽂혀있는 것이다. 이경우엔 그냥 스킵하면 된다.

❗ 주의할 점

실수하기 쉬운게, 처음에 플러그에 제품을 꽂을때도 신경을 써줘야 한다는 것이다. 이경우에도 꽂혀있으면 안꽂아도 된다. 처음부터 플러그 구멍 갯수만큼 꽂고 시작하는게 아니다

그리고 아래 내 코드에서 파이썬의 슬라이스를 이용해 뒷순서에 제품이 존재 하면 그 인덱스를 구하는 부분이 있다. 이렇게

idx = max(idx, product[i + 1:].index(v) + i + 1)

지금 리스트를 잘랐으니까, 인덱스가 원래 리스트와 동일하지 않다.

# 원본
li = [1, 2, 3, 4, 5] # 3의 index -> 2
# 슬라이스 한 것
li[2:] = [3, 4, 5] # 3의 index -> 0

자른만큼 더해줘야 한다 꼭!

📃 소스코드

import sys
    
N, K = map(int, input().split())
product = list(map(int, input().split()))
multitab = [0] * N
result = 0

for i in range(K):
    # 꽂혀있으면 안뽑아도됨
    if product[i] in multitab:
        continue
    # 멀티탭에 비어있는 자리있으면 꽂음
    elif 0 in multitab:
        multitab[multitab.index(0)] = product[i]
    # 꽉차있는데 꽂혀있지도 않음. 뽑아야함
    else:
        idx = -sys.maxsize
        isExist = True # 등장함/안함 판별
        for k, v in enumerate(multitab):
            if v not in product[i + 1:]:
                # 앞으로 등장 안하는 가전제품은
                multitab[k] = product[i] # 뽑아버림
                isExist = False
                break
            else:
                # 최대한 나중에 등장하는것 찾기
                # idx는 order의 인덱스
                idx = max(idx, product[i + 1:].index(v) + i + 1)
        if idx != -sys.maxsize and isExist == True:
            multitab[multitab.index(product[idx])] = product[i] # 뽑기   
        result += 1 # 뽑았으니 1증가

print(result)

카카오페이로 커피사기 ❤️ 토스,계좌로 커피사기 ❤️