백준 온라인 저널, 그리디 알고리즘/1700번 : 멀티탭 스케줄링(파이썬) / 백준 골드 문제

문제 정의

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

 

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

1. 키보드
2. 헤어드라이기
3. 핸드폰 충전기
4. 디지털 카메라 충전기
5. 키보드
6. 헤어드라이기

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

 

 

입력

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

 

 

출력

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

 

 

예제 입력 1

2 7
2 3 2 3 1 2 7

예제 출력 1

2

- 해당 문제는 n과 k의 범위가 최대 100이기에 삼중 반복문을 사용하더라도 시간 제한에 걸리지 않는다.

 

 

 

 

접근 방법

1. n > k인 경우 플러그를 뺄 필요가 없으므로 0을 출력한다.
2-1. n < k인 경우 n만큼 플로그를 꽂고 뒤에 현재 플러그에 꽂은 전기 용품이 있다면 그대로 놔두고 다음 전기 용품을 확인한다.
2-2. n < k인 경우 n만큼 플로그를 꽂고 뒤에 현재 플러그에 꽂은 전기 용품이 없다면 계속해서 다음 전기용품을 확인하면서 현재 플러그에 꽂은 전기 용품 중 가장 먼저 나오는 전기 용품을 제외한 나머지 전기 용품들을 탐색한다.
2-3. 이후 가장 늦게 나오거나 나오지 않은 전기 용품 중에서 하나를 뽑아 다음 전기 용품을 꽂는다.

 

 

코드

# 1. n > k인 경우 플러그를 뺄 필요가 없으므로 0 출력
# 2-1. n < k인 경우 n만큼 플로그를 꽂고 뒤에 현재 플러그에 꽂은 전기 용품이 있다면 그대로 놔두고 다음 전기 용품을 확인한다.
# 2-2. n < k인 경우 n만큼 플로그를 꽂고 뒤에 현재 플러그에 꽂은 전기 용품이 없다면 계속해서 다음 전기용품을 확인하면서 현재 플러그에 꽂은 전기 용품 중 가장 먼저 나오는 전기 용품을 제외한 나머지 전기 용품들을 탐색한다.
# 2-3. 이후 가장 늦게 나오거나 나오지 않은 전기 용품 중에서 하나를 뽑아 다음 전기 용품을 꽂는다.
# 해당 문제는 n과 k의 범위가 최대 100이기에 삼중 반복문을 사용하더라도 괜찮다.

import sys
n, k = map(int, sys.stdin.readline().split())
array = list(map(int, sys.stdin.readline().split()))
multitap = []
priority = [0 for _ in range(n)] # 멀티탭에 꽂혀있는 전기용품에 대해 우선순위를 정해준다.
unplug_count = 0

if n >= k:
    print(0)
else:
    # 써야할 전기용품을 차례대로 탐색한다.
    for i in range(len(array)):
        # 해당 전기 용품이 현재 멀티탭에 꽂혀있는지 확인한다.
        if array[i] not in multitap:
            # 현재 멀티탭에 꽂혀있는 전기 용품이 구멍 개수보다 작은 지 확인한다.
            if len(multitap) < n:
                multitap.append(array[i]) # 현재 멀티탭에 꽂혀있는 전기 용품이 구멍 개수보다 작은 경우 멀티탭에 꽂는다.
            # 이미 남아있는 멀티탭 구멍이 없는 경우
            else:
                # 현재까지 탐색한 전기용품 다음 인덱스의 전기용품들을 확인한다.
                count_of_electonic_in_multitap = 0
                for j in range(i, len(array)):
                    # 만약 탐색 중간에 멀티탭에 꽂혀있는 전기 용품을 발견한다면 해당 전기 용품의 우선순위를 정해준다.                 
                    for k in range(len(multitap)):
                        if array[j] == multitap[k] and priority[k] == 0:
                            priority[k] = j
                            count_of_electonic_in_multitap += 1
                # 만약 멀티탭에 꽂혀있는 전기용품을 발견하지 못한 게 있다면 멀티탭에 꽂혀있는 전기 용품 나중에 사용하지 않는 전기용품을 빼준다.
                if count_of_electonic_in_multitap == n:
                    multitap.pop(priority.index(max(priority)))
                # 멀티탭에 꽂혀있는 전기
                else:
                    multitap.pop(priority.index(0))
                priority = [0 for _ in range(n)]
                unplug_count += 1 # 플러그를 하나 뽑아준다.
                multitap.append(array[i])  # 이후 멀티탭에 전기용품을 꽂아준다.
    print(unplug_count)

- 처음 풀어보는 백준 골드 1레벨 문제였다. 하지만 하나 하나 차근차근 짚어가며 코드를 짜니 생각보다 어렵지 않게 풀었다. 다시 한번 정리하면서 하는 것이 중요하다는 것을 느낀다.