백준 1700 멀티탭 스케줄링

출처: www.acmicpc.net/problem/1700

분류: 그리디

---

접근방식

플러그의 개수와 사용해야 할 기기들의 순서가 주어질 때 플러그를 최소한으로 뽑을 수 있는 횟수를 찾는 문제입니다.

저는 처음에 단순히 앞으로 사용될 횟수가 가장 적은 플러그를 빼면 되지 않을까 생각했지만, 

그렇게 하면 다음과 같은 경우에 최적의 경우가 되지 못합니다.

2 1 3 1 3 1 3 2222....

이런 경우라면 2 1 3 중에서 사용 횟수는 1과 3이 가장 적지만 2는 나중에 나오기 때문에 당장 2를 뽑아서 사용해야 합니다.

뽑혀있는 플러그 중에서 가장 나중에 사용될 아이를 찾아야 합니다.

플러그를 뽑아야 할 상황이 오면 현재 꽂아야 할 기기 다음부터 확인해서 가장 나중에 사용될 플러그의 인덱스를 찾습니다. 

가장 나중에 뽑히는 인덱스를 기억해뒀다가 이보다 큰 인덱스가 나오면 이걸로 바꿔주면 되겠죠!

만약 사용되지 않는다면 즉시 뽑아버리면 됩니다.

 

이걸 이해했다면 알고리즘의 순서는 다음과 같이 정리해볼 수 있습니다.

1. 사용할 기기가 이미 플러그에 꽂혀있는지 확인한다.

2. 사용할 수 있는 플러그가 남아있다면 꽂는다.

3. 사용할 수 있는 펄 러그가 없다면 꽂혀있는 플러그 중 가장 나중에 사용될 기를 뽑는다.

 

해결방법

let n = readLine()!.split(separator: " ").map{Int($0)!}
let usageList = readLine()!.split(separator: " ").map{Int($0)!}

var plug = [Int]()
var offCount = 0

for (i, e) in usageList.enumerated() {
  if plug.contains(e) {
    continue
  } else if plug.count < n[0] {
    plug.append(e)
  } else {
    /// 이제 뺄 아이를 정해야 한다.
    // 가장 나중에 사용될 아이를 찾는다.
    // 사용되지 않았다면(그대로 -1) 바로 빼버린다.
    var offIndex = -1
    var lastUsed = -1
    for (plugIndex, p) in plug.enumerated() {
      var shouldUsed = -1
      
      for plugUsedIndex in i+1..<usageList.count {
        if p == usageList[plugUsedIndex] {
          shouldUsed = plugUsedIndex
          break
        }
      }
      
      // 앞으로 사용되지 않는다면 얘를 빼버린다.
      if shouldUsed == -1 {
        offIndex = plugIndex
        break
      } else {
        if shouldUsed > lastUsed {
          lastUsed = shouldUsed
          offIndex = plugIndex
        }
      }
    }
    
    plug[offIndex] = e
    offCount += 1
  }
}

print(offCount)

 

배운점

어젠가 이틀 전인가 도전했다가 다른 분들의 풀이를 봐도 도저히 이해가 안 가서 포기했던 문제였는데

오늘 다시 도전해보니까 생각보다 금방 풀었습니다.

알고리즘은 역시 집중력도 중요한 것 같아요.

저는 아직 어느정도 수준이 안 되었기 때문에 한 문제를 너무 오래 붙잡고 있는 것보다는 적당히 해보다가 안 되면 다른 분들의 풀이를 보고 풀고 그래도 이해가 안되면... 과감히 넘어가서 나중에 다시 도전해보는 것도 좋은 것 같습니다. 우선은 최대한 많이 풀어보고 공부하는게 중요.... 

화이팅