[그리디] 코딩테스트 문제 TIL (멀티탭 스케줄링) - 백준 1700번

말하는 감자·2024년 12월 30일

TIL algorithm baekjoon greedy python 구현 그리디 백준 알고리즘 코딩테스트 코딩테스트 준비 파이썬

코딩테스트 유형별 풀이

목록 보기

62/67

이번 문제는 아이디어는 금방 떠올랐지만 구현이 꽤 어려웠던 문제입니다. 그리고 제가 풀었던 백준 문제중 가장 티어가 높은 문제이기도 합니다. 그럼 살펴볼까요?

1. 오늘의 학습 키워드

그리디
구현

2. 문제: 1700. 멀티탭 스케줄링

단계: 🥇 골드 1단계
주제:
- 그리디 알고리즘
출처: https://www.acmicpc.net/problem/1700

문제

기숙사에서 살고 있는 준규는 한 개의 멀티탭을 이용하고 있다. 준규는 키보드, 헤어드라이기, 핸드폰 충전기, 디지털 카메라 충전기 등 여러 개의 전기용품을 사용하면서 어쩔 수 없이 각종 전기용품의 플러그를 뺐다 꽂았다 하는 불편함을 겪고 있다. 그래서 준규는 자신의 생활 패턴을 분석하여, 자기가 사용하고 있는 전기용품의 사용순서를 알아내었고, 이를 기반으로 플러그를 빼는 횟수를 최소화하는 방법을 고안하여 보다 쾌적한 생활환경을 만들려고 한다.

예를 들어 3 구(구멍이 세 개 달린) 멀티탭을 쓸 때, 전기용품의 사용 순서가 아래와 같이 주어진다면,

키보드
헤어드라이기
핸드폰 충전기
디지털 카메라 충전기
키보드
헤어드라이기

키보드, 헤어드라이기, 핸드폰 충전기의 플러그를 순서대로 멀티탭에 꽂은 다음 디지털 카메라 충전기 플러그를 꽂기 전에 핸드폰충전기 플러그를 빼는 것이 최적일 것이므로 플러그는 한 번만 빼면 된다.

입력

첫 줄에는 멀티탭 구멍의 개수 N (1 ≤ N ≤ 100)과 전기 용품의 총 사용횟수 K (1 ≤ K ≤ 100)가 정수로 주어진다. 두 번째 줄에는 전기용품의 이름이 K 이하의 자연수로 사용 순서대로 주어진다. 각 줄의 모든 정수 사이는 공백문자로 구분되어 있다.

출력

하나씩 플러그를 빼는 최소의 횟수를 출력하시오.

예제 입력 1

2 7
2 3 2 3 1 2 7

예제 출력 1

3. 문제 풀이

Step1. 문제 이해하기

이 문제는 멀티탭 구멍의 제한된 수로 인해 특정 전기용품을 사용하기 위해 플러그를 뽑아야 하는 상황에서, 플러그를 뽑는 횟수를 최소화하는 문제입니다.

입출력은 다음과 같습니다:

Input:
- 첫 줄에는 멀티탭 구멍의 개수(N)와 전기 용품의 총 사용횟수(K)가 정수로 주어집니다.
  - N은 1이상 100이하, K는 1이상 100이하입니다.
- 두 번째 줄에는 전기 용품의 이름이 K이하의 자연수로 사용 순서대로 주어집니다.
Output:
- 하나씩 플러그를 빼는 최소의 횟수를 출력합니다.

Step2. 문제 분석하기

멀티탭에는 최대 N개의 플러그만 꽃을 수 있습니다. 전기 용품이 멀티탭에 이미 꽃혀 있다면, 아무작업도 필요하지 않습니다.
멀티탭에 비어 있는 구멍이 있다면, 현재 사용하려는 전기 용품을 플러그에 꽃습니다.
만약 멀티탭에 자리가 없다면 다음과 같은 조건을 생각해야 합니다.
1. 플러그를 하나 빼야 하므로, 어떤 플러그를 뽑을지 결정해야 합니다.
2. 앞으로 사용되지 않거나, 사용된다면 가장 늦게 사용될 플러그를 우선적으로 뽑아야 뽑는 횟수를 최소화 할 수 있습니다.

예시를 통해 확인해보겠습니다.

N = 2, K = 7
2, 3, 2, 3, 1, 2, 7

일단 2, 3 전기 용품을 플러그에 꽃습니다.
그 다음 2, 3이 나오는데 이는 이미 플러그에 꽃혀있기 때문에 플러그를 뽑을 필요가 없습니다.
1번 전기 용품이 나왔습니다. 그런데 플러그에는 이미 2, 3번 전기 용품이 꽃혀 있습니다.
3번 전기 용품은 앞으로 사용되지 않습니다. 그렇기 때문에 3번 전기 용품 플러그를 뽑고, 1번 전기 용품을 꽃습니다.
2번 전기 용품은 꽃혀있기 때문에 뽑을 필요가 없습니다.
7번 전기 용품 사용을 위해 1번 전기 용품을 뽑습니다.

최종적으로 플러그를 뽑는 횟수는 2번입니다.

따라서, 플러그 뽑기 전략을 정리하자면 다음과 같습니다.

멀티탭에 꽃혀 있는 전기용품들 중에서, 가장 나중에 사용되거나 더이상 사용되지 않는 전기 용품을 뽑습니다.
이를 위해 현재 사용 순서 이후의 전기 용품 사용 여부를 탐색해야 합니다.

Step3. 코드 설계

입력으로 멀티탭 구멍 수 N, 전기용품 사용 순서 K를 받습니다.
멀티탭 상태를 나타내는 리스트를 초기화합니다.
전기용품 사용 순서를 따라가며:
- 이미 멀티탭에 꽂혀 있다면, 아무 작업도 하지 않습니다.
- 멀티탭에 빈 자리가 있다면, 해당 전기용품을 멀티탭에 추가합니다.
- 멀티탭이 가득 찬 경우, 어떤 플러그를 뽑을지 결정하여 플러그를 뽑고 새로운 전기용품을 꽂습니다.
플러그를 뽑은 횟수를 출력합니다.

Step4. 코드 구현

import sys
N, K = map(int, sys.stdin.readline().split())
devices = list(map(int, sys.stdin.readline().split()))
def sol(N, K, devices):
    multitap = []
    cnt = 0
    for i in range(K):
        current_device = devices[i]
        
        if current_device in multitap:
            continue
        
        if len(multitap) < N:
            multitap.append(current_device)
            continue
        
        not_used_in_future = -1
        far_index = -1
        
        for device in multitap:
            # 미래에 사용되지 않을 전기용품
            if device not in devices[i + 1:]:
                not_used_in_future = device
                break
            # 미래에 사용될 전기용품
            else:
                index = devices[i + 1:].index(device)
                if index > far_index:
                    far_index = index
                    not_used_in_future = device
                
        
        multitap.remove(not_used_in_future)
        cnt += 1
        multitap.append(current_device)
    return cnt
print(sol(N=N, K=K, devices=devices))

코드 설명:
- 초기화:
  - multitap 리스트는 현재 멀티탭에 꽂혀 있는 전기용품을 저장합니다.
  - cnt는 플러그를 뽑는 횟수를 기록합니다.
- 전기용품 사용 순서 순회:
  - current_device는 현재 사용하려는 전기용품입니다.
  - 이미 멀티탭에 꽂혀 있는 경우:
    - 작업이 필요 없으므로 continue로 다음 반복으로 넘어갑니다.
  - 멀티탭에 빈 자리가 있는 경우:
    - 현재 전기용품을 멀티탭에 추가합니다.
  - 멀티탭이 꽉 찬 경우:
    - 어떤 전기용품을 뽑을지 결정해야 합니다.
- 멀티탭에 꽉 찬 경우의 처리:
  - not_used_in_future 변수는 뽑을 전기용품을 저장합니다.
  - far_index는 멀티탭에 꽂혀 있는 전기용품 중 가장 나중에 사용될 전기용품의 인덱스를 저장합니다.
  - 멀티탭에 꽂힌 모든 전기용품에 대해:
    - 미래에 사용되지 않을 전기용품을 발견하면 즉시 뽑기로 결정합니다 (break).
    - 그렇지 않으면, 미래에 가장 나중에 사용될 전기용품을 업데이트합니다.
  - 최종적으로 선택한 전기용품을 멀티탭에서 제거하고 cnt를 증가시킵니다.
  - 현재 전기용품을 멀티탭에 추가합니다.
- 결과 반환:
  - 플러그를 뽑은 횟수 cnt를 반환합니다.
시간 복잡도:
- 멀티탭 관리:
  - 멀티탭에 새로운 전기용품을 꽂거나 제거하는 작업은 최대 N번 수행됩니다.
- 미래 사용 확인:
  - 각 전기용품에 대해, devices[i+1:]에서 미래에 사용될 인덱스를 확인하는 작업은 최대 K번 호출됩니다.
  - 각 호출에서 리스트의 나머지 부분을 탐색해야 하므로, 최악의 경우 O(K) 시간이 소요됩니다.
- 총 시간 복잡도:
  - 외부 반복문은 K번 수행됩니다.
  - 내부의 미래 사용 확인은 최악의 경우 N×K번 비교를 수행합니다.
  - 결과적으로 시간 복잡도는 $O(N \times K)$ 입니다.
결과:

4. 마무리

이번 문제는 멀티탭의 제한된 구멍 수를 고려하여 전기용품 사용 순서를 최적화하는 그리디 알고리즘 문제였습니다. 플러그를 뽑는 횟수를 최소화하기 위해, 현재 멀티탭에 꽂힌 전기용품 중 가장 나중에 사용되거나 더 이상 사용되지 않는 전기용품을 선택적으로 뽑는 전략을 사용했습니다. 이를 위해 리스트와 반복문을 활용해 미래의 사용 여부를 확인하며 구현했습니다. 문제의 시간 복잡도는 O(N × K)이지만, 실제 실행 속도는 제한된 범위 내에서 적절히 작동하여 효율적이었습니다. 이 문제를 통해 탐욕적 선택 전략의 실질적인 응용과 최적화를 위한 구현 방법을 익힐 수 있었습니다.

긴 글 읽어주셔서 감사합니다.