백준 - 멀티탭 스케줄링(Swift)

백준 - 멀티탭 스케줄링(Swift)

 

 

 문제 설명

 

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

1700번: 멀티탭 스케줄링

 

 

 

 

 나의 풀이

 

 

문제의 핵심을 찾는게 버거웠던 문제이다.

처음에는 단순히 뒤에 있는 리스트 중에서 가장 적게 사용한 것을 빼자고 생각했는데

2 3 2 3 1 1 5 5 6 6 10 ... 2 2 2 의 경우에 가장 나중에 나오는 2를 빼야하는데 전체적으로 봤을때 2의 수가 가장 많기 때문에 가장 늦게 뺌으로써 최적을 달성하지 못한다.

 

그래서 이 문제는 그리디한 접근으로 가장 나중에 사용되는 것을 먼저 뽑아야 한다는 아이디어를 생각해야한다. 이렇게 되면 반례가 없게되고 매순간 최적으로 답에 도달할 수 있게 된다.

 

Set자료구조를 이용한 다른 사람의 풀이를 보고 굉장히 참신하다고 생각이 들었다.

 

기존의 원리는 이렇다.

문제의 예시로 2개의 콘센트와 2 3 2 3 1 2 7의 순서로 들어온다고 했을때

처음에는 2 3이 있게 된다.

그리고 이후 2와 3이나올 때는 무시하고 지나가고 2와 3이 아닐때(여기서는 1이 들어와야할때) 1의 뒤에 인덱스를 탐색하면서 가장 마지막에 사용되는 전자기기를 빼준다. 만약 이후 사용되지 않는 전자기기가 현재 콘센트에 뽑혀있다면 그걸 뺴준다.

 

이 구조를 편하게 Set으로 표현했다.

현재 콘센트에 담고 있는 것을 Set으로 놓아 변수 temp으로 둔 뒤 인덱스를 탐색하는데 temp안에 값이 있다면 temp에서 그 값을 바로 제거를한다. 그리고 temp의 count가 1일때 break를 해주고 그 값을 콘센트에서 지운다. 

이렇게 한다면 가장 마지막에 사용되는 전자기기만 남겨둘 수 있고, 만약 마지막에 사용되는 전자기기가 하나도 없는 경우에도 temp.first를 통해 아무거나 지울 수 있기 때문에 논리가 가능해진다.

 

import Foundation

let input = readLine()!.components(separatedBy:" ").map{Int($0)!}
let N = input[0], K = input[1]
let usageList = readLine()!.components(separatedBy:" ").map{Int($0)!}

var keep = [Int]()
var cnt = 0
for (i, plug) in usageList.enumerated() {
    if keep.contains(plug) {
        continue
    } else if keep.count < N {
        keep.append(plug)
    } else {
        var temp = Set(keep)
        for j in i+1..<K {
            if temp.count == 1 { break }
            if temp.contains(usageList[j]) {
                temp.remove(usageList[j])
            }
        }
        keep.remove(at: keep.firstIndex(of: temp.first!)!)
        keep.append(usageList[i])
        cnt += 1
    }
}
print(cnt)

 

 

 

 다른 사람의 풀이

 

import Foundation

let input = readLine()!.components(separatedBy:" ").map{Int($0)!}
let N = input[0], K = input[1]
let usageList = readLine()!.components(separatedBy:" ").map{Int($0)!}

var keep = [Int]()
var cnt = 0
for (i, plug) in usageList.enumerated() {
    if keep.contains(plug) { // 콘센트에 꽂혀있으면 넘어가고
        continue
    } else if keep.count < N { // 콘센트가 꽉차지않았다면 추가
        keep.append(plug)
    } else {
        var offIndex = -1 // 콘센트 인덱스
        var lastUsed = -1 // 콘센트에 꽂혀있는 값들을 탐색하면서 더 큰 인덱스가 무엇인지 찾기위한 변수
        
        for (plugIndex, p) in keep.enumerated() {
            var shouldIndex = -1
            for j in i+1..<K {
                if p == usageList[j] { //콘센트에 꽂혀있는 게 특정인덱스에서 사용이 되었다면 인덱스 보관
                    shouldIndex = j 
                    break
                }
            }
            if shouldIndex == -1 { // 현재 탐색하고 있는 콘센트에 꽂힌 숫자가 이후에 없다면 break
                offIndex = plugIndex
                break
            } else {
                if shouldIndex > lastUsed { //이전에 꽂혀있던 인덱스보다 높다면 갱신.
                    lastUsed = shouldIndex
                    offIndex = plugIndex
                }
            }
        }
        keep[offIndex] = plug
        cnt += 1
        
    }
}
print(cnt)

 

 피드백

 

좀 어려워서 다른사람의 풀이를 찾아보고 문제를 풀었다.

문제의 특성상 콘센트가 꽉차는 것을 먼저 if문에 두는 것이 아닌 콘센트에 이미 값이 있다면 continue하는 로직을 먼저 넣어줘야했다. 

 

그리고 문제를 Set을 이용해서 단순화 시킨 점이 재밌었는데 나도 유연한 사고를 가지려고 노력해야겠다.