[Algorithm] 백준 - 1700번 멀티탭 스케줄링 (Swift)

🤓 문제

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

✨ 풀이

캐싱과 느낌이 정말 비슷하다. 왜냐하면 멀티탭에 꽂혀있느면 바로 사용이 가능한 것이고(Hit), 멀티탭에 없으면 플러그를 꽂아야 한다. 하지만 코드는 한정적이기 때문에 효과적으로 멀티탭을 관리해야 한다.

 

첫번째 풀었던 방법은 캐싱을 생각하면서 가장 사용이 많이 된 것을 남기고 나머지를 교체하는 알고리즘을 사용했지만 이 문제의 중요한 점은 미래를 안다는 것이다. 미래를 모르는 상황에서는 가장 사용이 많이 되거나 가장 최근에 사용한 것을 살리는 식으로 캐싱을 하면 되지만 미래를 아는 순간 이야기는 달라진다.

 

멀티탭이 꽉차게 되면 가장 늦게 쓰는 플러그를 빼면 된다. 어자피 가장 최근에 쓰는건 결국 사용하기 때문에 일단 넣어두어야 한다. 가장 늦게 사용하는 플러그는 일단 필요가 없으므로... 빼면 된다!

let nk = readLine()!.split(separator: " ").compactMap { Int($0) }
let (n, k) = (nk[0], nk[1])
let plugs = readLine()!.split(separator: " ").compactMap { Int($0) }

var answer = 0
var powerStrip: Set<Int> = []

for i in 0..<k {
    guard !powerStrip.contains(plugs[i]) else { continue }

    if valid.count == n {
        var element = 0
        var index = 0

        for j in valid {
            let firstIndex = plugs[i...].firstIndex(of: j) ?? k

            if index < firstIndex {
                element = j
                index = firstIndex
            }
        }

        powerStrip.remove(element)
        answer += 1
    }

    powerStrip.insert(plugs[i])
}

print(answer)

💡 결과

N의 최댓값이 100이라서 firstIndex(of:)를 사용해도 큰 문제 없었다.