[알고리즘/Swift] 1700 멀티탭 스케줄링
문제 정보
- 문제 출처: 백준 온라인 저지
- 문제 링크: 1700 멀티탭 스케줄링
- 제출 언어: Swift
- 알고리즘 분류:
- 그리디 알고리즘
풀이
그리디 알고리즘
Greedy
는 ‘탐욕스러운’이란 뜻으로, 선택의 순간마다 당장 주어진 상황중 최선의 solution이라고 판단되는 것을 선택하는 알고리즘이다- 가장 최선의 solution만을 계산하므로 메모리 사용량이 적다
- 빠르지만 최적의 해 solution을 보장할 수는 없다 -> 각 단계마다 선택한 최적해가 전체 최적해를 만든다는 보장은 할 수 없음
- 동작과정
- 해 선택 : 현재 상태에서 부분 문제의 최적해를 구한 뒤, 이를 부분해 집합에 추가한다
- 실행 가능성 검사 : 새로운 부분해 집합이 실행 가능한지 확인하고, 문제의 제약 조건을 위반하지 않았는지 검사한다
- 해 검사 : 새로운 부분해 집합이 문제의 해가 되는지 확인하고 아직 전체 문제의 해가 완성되지 않았다면 해 선택 과정부터 다시 시작한다
나만의 알고리즘
이 문제를 접했을 때 나만의 알고리즘을 짜서 풀어보자 생각을 했다 그래서 내가 생각한 알고리즘은 다음과 같다
입력받은 전자기기 리스트에서 하나씩 꽂으려고 하면서
case1. 꽂을 경우
- 빈 공간이 있으면 그냥 남는 곳에 꽂는다
- 이미 꽂혀있는 경우 넘어간다
- 플러그 공간이 모두 찼을 경우 뽑는다 -> 뽑는 경우 고려
case2. 뽑는 경우
- 모든 플러그 나중에 안 사용되면 아무거나 뽑기
- 모든 플러그 나중에 써야되면 좀 더 나중에 사용되는 것 뽑기
- 몇 개만 나중에 써야되면 안 사용되는 것 뽑기
이런 식으로 경우의 수를 나누어 보았다
case2
좀 더 자세히 작성해보자
여기서 temp
는 뽑는 플러그 후보, far
은 가장 나중에 사용되는 전자기기, idx
는 고려하고 있는 plug의 idx번호라고 생각하면 된다
모든 Plug를 돌면서 현재 꽂으려는 전자기기 이후로 해당 Plug 꽂힌 전자기기가 사용되지 않을 경우 temp = p
를 해주고 break
를 해준다
이것은 당연히 나중에 사용되지 않는 전자기기는 가장 강력한 뽑히는 Plug 후보가 된다
그것이 아니라면 얼마나 나중에 사용되는지 고려를 해야하는 데 이때, idx가 far보다 멀 경우 또 뽑힐 수 있는 Plug의 후보가 될 수 있다
그 때 far = idx
, temp = p
를 해준다
모든 플러그를 돌고나면 temp
에 있는 플러그를 뽑아주고 꽂으려는 전자기기를 꽂아준 후 count += 1
을 해주면 된다
그리디 적용
- 해 선택 : 현재 플러그에 꽂힌 전자기기중 나중에 재사용되는 전자기기를 선택 -> 뽑는 전자기기 후보에 추가
- 실행 가능성 검사 : 해당하는 전자기기가 가장 나중에 재사용되는 기기인지 검사한다
- 해 검사 : 확인한 전자기기가 꽂아야 하는 마지막 전자기기인지 확인하고 아닐경우, 다음 전자기기로 넘어가서 해선택부터 수행한다
전체 코드
import Foundation
let n = readLine()!.split(separator: " ").map{Int(String($0))!}
let (N,K) = (n[0], n[1])
var plug: [Int] = []
let elec: [Int] = Array(readLine()!.split(separator: " ").map{Int(String($0))!})
var count = 0
for i in 0..<K{
if plug.contains(elec[i]){
continue
}
if plug.count != N{
plug.append(elec[i])
continue
}
var temp = 0
var far = 0
for p in plug{
if !elec[i...].contains(p){
temp = p
break
}
let idx = elec[i...].firstIndex(of: p)!
if idx > far{
far = idx
temp = p
}
}
plug.remove(at: plug.firstIndex(of: temp)!)
plug.append(elec[i])
count += 1
}
print(count)