문제 정보


image

풀이

그리디 알고리즘

  • Greedy는 ‘탐욕스러운’이란 뜻으로, 선택의 순간마다 당장 주어진 상황중 최선의 solution이라고 판단되는 것을 선택하는 알고리즘이다
  • 가장 최선의 solution만을 계산하므로 메모리 사용량이 적다
  • 빠르지만 최적의 해 solution을 보장할 수는 없다 -> 각 단계마다 선택한 최적해가 전체 최적해를 만든다는 보장은 할 수 없음
  • 동작과정
    • 해 선택 : 현재 상태에서 부분 문제의 최적해를 구한 뒤, 이를 부분해 집합에 추가한다
    • 실행 가능성 검사 : 새로운 부분해 집합이 실행 가능한지 확인하고, 문제의 제약 조건을 위반하지 않았는지 검사한다
    • 해 검사 : 새로운 부분해 집합이 문제의 해가 되는지 확인하고 아직 전체 문제의 해가 완성되지 않았다면 해 선택 과정부터 다시 시작한다

나만의 알고리즘

이 문제를 접했을 때 나만의 알고리즘을 짜서 풀어보자 생각을 했다 그래서 내가 생각한 알고리즘은 다음과 같다
입력받은 전자기기 리스트에서 하나씩 꽂으려고 하면서

case1. 꽂을 경우

  1. 빈 공간이 있으면 그냥 남는 곳에 꽂는다
  2. 이미 꽂혀있는 경우 넘어간다
  3. 플러그 공간이 모두 찼을 경우 뽑는다 -> 뽑는 경우 고려

case2. 뽑는 경우

  1. 모든 플러그 나중에 안 사용되면 아무거나 뽑기
  2. 모든 플러그 나중에 써야되면 좀 더 나중에 사용되는 것 뽑기
  3. 몇 개만 나중에 써야되면 안 사용되는 것 뽑기

이런 식으로 경우의 수를 나누어 보았다
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)