코딩테스트 연습 - 체육복

문제 풀이 아이디어

전체 아이디어: 그리디 알고리즘

체육복을 빌릴 수 있는 사람이 번호가 -1 혹은 +1인 사람이기 때문에 체육복을 빌려야하는 사람 입장에서는 빌릴 수 있는 대상이 정해져있습니다.

체육복을 잃어버린 사람이 오름차순으로 정렬되어 있다고 할 때 n번 사람은 체육복을 n - 1 혹은 n + 1에게 빌릴 수 있습니다. 만약에 둘 다에게 빌릴 수 있다면 n - 1에게 빌려야 수업을 들을 수 있는 사람을 최대화할 수 있습니다. 왜냐하면 n보다 큰 번호의 사람은 (= n + 1) n - 1에게 빌릴 수 없기 때문입니다.

따라서 체육복을 잃어버린 사람을 정렬하고 작은 번호의 사람부터 빌려가면서 그리디 알고리즘을 실행하면 됩니다.

❗️주의

이 문제에서 주의할 점은 lost와 reserve에 둘 다 속하는 학생이 있을 수 있다는 점입니다. 만약에 겹치는 사람이 있다면 그 사람은 잃어버리지도 않았고 빌려줄 수도 없는 사람이므로 각각의 배열에서 삭제하고 그리디 알고리즘을 실행해야 합니다.

코드

import Foundation

func solution(_ n:Int, _ lost:[Int], _ reserve:[Int]) -> Int {
    var count = n
    
    // 진짜로 잃어버린 사람, 진짜로 빌려줄 수 있는 사람을 구한다.
    let realLost = lost.filter { !reserve.contains($0) }.sorted()
    var realReserve = reserve.filter { !lost.contains($0) }.sorted()
    
    // 진짜로 잃어버린 사람을 순회하면서 체육복을 빌릴 수 없는 사람을 찾는다.
    for student in realLost {
        // 자기보다 작은 사이즈 빌릴 수 있음
        if realReserve.contains(student - 1) {
            realReserve.removeAll { $0 == student - 1 } //👉 빌려줄 수 있는 사람에서 제거
        // 자기보다 큰 사이즈 빌릴 수 있음
        } else if realReserve.contains(student + 1) {
            realReserve.removeAll { $0 == student + 1 } //👉 빌려줄 수 있는 사람에서 제거
        // 빌릴 수 없음
        } else {
            count -= 1 //👉 빌릴 수 없다면 수업들을 수 있는 사람 - 1
        }
    }
    
    return count
}