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

📖 문제

---

🧑🏻‍💻 풀이 과정

1) 문제 접근 및 이해

해당 문제를 처음 접했을 때, 앞으로 사용할 숫자들을 순환하면서 앞으로 사용하지 않거나 가장 적게 사용하는 숫자들을 제거하도록 구성하였습니다.

그러나 적게 사용하지만 일정 주기마다 해당 숫자를 사용해야하는 특정 상황이 발생하면, 해당 숫자를 위해 계속해서 값을 변경해주어야 합니다.

이로 인하여 최소 교환 횟수를 구하기 어려웠습니다.

 

위의 방법을 보완하여 앞으로 사용하지 않거나, 가장 나중에 사용하는 숫자를 우선적으로 제거하도록 하였습니다.

2) 알고리즘

• 그리디

3) 풀이 코드

사용 언어 - Python

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


# 가장 나중에 사용되거나 앞으로 사용하지 않을 숫자 반환
def get_far_num(arr):
    idxs = {}

    for p in plug:
        if p not in arr:
            return p
        else:
            k = arr.index(p)
            idxs[k] = p

    max_key = max(idxs.keys())
    return idxs[max_key]


# 입력 데이터
N, K = map(int, sys.stdin.readline().split())
li = list(map(lambda x: int(x)-1, sys.stdin.readline().split()))

answer = 0

# 플러그 꽂아진 숫자들
plug = set()
for idx in range(K):
    # 다음에 사용할 번호
    next = li[idx]

    # 이미 플러그에 꽂아서 사용중이면 아무 동작 안함
    if next in plug:
        pass
    # 플러그 모두 사용중 아니라면 추가
    elif len(plug) < N:
        plug.add(next)
    # 가장 나중에 사용되거나 앞으로 사용되지 않을 숫자 삭제 및 새로 추가
    else:
        num = get_far_num(li[idx+1:])
        plug.remove(num)
        plug.add(next)
        answer += 1


print(answer)

---

🔗 문제 링크

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

1700번: 멀티탭 스케줄링

 

 

※ 오류 및 오타, 다른 의견이 있는 경우 댓글을 남겨주시면 감사하겠습니다