백준 1700번 - 멀티탭 스케줄링 (Go)

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

분석

이 문제는 멀티탭 구멍의 개수 n 과 전기 용품의 사용 순서 k 가 주어집니다. 멀티탭에 꽂혀 있는 플러그를 최소한으로 뽑으면서

k 개의 용품을 순서대로 사용해야 합니다.

 

미래의 사용 순서를 미리 알고 있기 때문에 가장 나중에 다시 사용되거나, 앞으로 사용되지 않을 용품을 먼저 뽑는 것이

최적의 해를 보장합니다.

 

알고리즘 실행 과정을 생각해보면,

1. 이미 꽂혀 있는 경우, 플러그를 뽑을 필요가 없으므로 continue
2. 빈 자리가 있는 경우, 그냥 꽂으면 됩니다.
3. 빈 자리가 없는 경우,
   1. 현재 멀티탭에 꽂힌 용품들 중, 가장 늦게 나타나는 용품을 찾습니다.
   2. 만약 이후에 다시 사용하지 않는 용품이 있다면 최우선 제거 대상 입니다. (풀이 코드의 인덱스를 최대값으로 줌)
   3. 찾은 용품을 뽑고 새 용품을 뽑습니다. 

시간 복잡도는 k 번 탐색 동안 멀티탭 구멍 n 개를 탐색하고, k 번 만큼 미래를 탐색하기 때문에 O(k * n * k) 입니다.

100 * 10000 = 1,000,000 이기 때문에 시간 제한은 넉넉하게 통과합니다.

공간 복잡도는 O(k) 만큼 저장합니다. 그리고 n 과 k 가 <= 100 이므로 아주 넉넉합니다.

풀이 코드

package main

import (
	"bufio"
	"fmt"
	"os"
)

func main() {
	in := bufio.NewReader(os.Stdin)
	out := bufio.NewWriter(os.Stdout)
	defer out.Flush()

	var n, k int
	fmt.Fscan(in, &n, &k)

	orders := make([]int, k)
	for i := 0; i < k; i++ {
		fmt.Fscan(in, &orders[i])
	}

	multitap := []int{}
	res := 0
	for i := 0; i < k; i++ {
		cur := orders[i]

		flag := false
		for _, v := range multitap {
			if v == cur {
				flag = true
				break
			}
		}

		if flag {
			continue
		}

		if len(multitap) < n {
			multitap = append(multitap, cur)
			continue
		}

		res++
		targetIdx := -1
		prevUsage := -1
		for j := 0; j < len(multitap); j++ {
			nextIdx := 101

			for l := i + 1; l < k; l++ {
				if multitap[j] == orders[l] {
					nextIdx = l
					break
				}
			}

			if nextIdx > prevUsage {
				prevUsage = nextIdx
				targetIdx = j
			}
		}

		multitap[targetIdx] = cur
	}

	fmt.Fprintln(out, res)
}

회고

미래를 탐색할때 기기의 우선순위를 어떻게 줄지 고민이 필요한 문제 였습니다.

다른 풀이를 참고 해보니, OS 의 페이지 교체 알고리즘이라는 것이 신기 했습니다.