새로운 블로그로 이전 작업을 진행하고 있어 포스트가 새로 작성되고 있지 않습니다.

빠른 시일 내에 새로운 블로그로 인사드리겠습니다.

새로운 블로그 : https://unho.vercel.app/

본문 바로가기
알고리즘 문제풀이/Python

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

by 언호 2022. 8. 16.

📖 문제


🧑🏻‍💻 풀이 과정

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번: 멀티탭 스케줄링

기숙사에서 살고 있는 준규는 한 개의 멀티탭을 이용하고 있다. 준규는 키보드, 헤어드라이기, 핸드폰 충전기, 디지털 카메라 충전기 등 여러 개의 전기용품을 사용하면서 어쩔 수 없이 각종 전

www.acmicpc.net

 

 

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

'알고리즘 문제풀이 > Python' 카테고리의 다른 글

[백준] 4195 친구 네트워크  (0) 2022.08.18
[백준] 1944 복제 로봇  (0) 2022.08.17
[백준] 2206 벽 부수고 이동하기  (0) 2022.08.15
[백준] 1504 특정한 최단 경로  (0) 2022.07.30
[백준] 1719 택배  (0) 2022.07.18

댓글