[Algorithm] 체육복 (탐욕법(Greedy))

🖥 문제

전체 학생의 수 n, 체육복을 도난당한 학생들의 번호가 담긴 배열 lost, 여벌의 체육복을 가져온 학생들의 번호가 담긴 배열 reserve가 매개변수로 주어질 때, 체육수업을 들을 수 있는 학생의 최댓값을 return 하도록 solution 함수를 작성해주세요.

🤔 풀이 방법

1. var possible = Array(repeating: 1, count: n)
   • n명의 학생이 모두 체육복을 하나씩 가져왔다고 가정하고 배열을 1로 초기화한다.
2. 도난당한 학생의 체육복을 -1해 주고 여벌 체육복이 있는 학생들의 체육복을 +1 해준다.

   for i in lost { possible[i - 1] -= 1 }
   for i in reserve { possible[i - 1] += 1 }

3. if i != 0 && possible[i - 1] == 2 && possible[i] == 0 {}
   • 2번 학생이 체육복이 없고, 1번 학생이 2개의 체육복을 가지고 있을 경우 2번 학생이 1번 학생에게 체육복을 빌린다.
4. else if i != n - 1 && possible[i] == 0 && possible[i + 1] == 2 {}
   • 2번 학생이 체육복이 없고, 1번 학생이 2개의 체육복을 가지고 있지 않을 경우
   • 3번 학생이 2개의 체육복을 가지고 있을 경우 2번 학생이 3번 학생에게 체육복을 빌린다.

👩🏻‍💻 Swift Code

import Foundation

func solution(_ n:Int, _ lost:[Int], _ reserve:[Int]) -> Int {
    var possible = Array(repeating: 1, count: n)
    var answer = 0

    for i in lost { possible[i - 1] -= 1 }
    for i in reserve { possible[i - 1] += 1 }

    for i in 0..<n {
        if i != 0 && possible[i - 1] == 2 && possible[i] == 0 {
            possible[i - 1] = 1
            possible[i] = 1
        } else if i != n - 1 && possible[i] == 0 && possible[i + 1] == 2 {
            possible[i] = 1
            possible[i + 1] = 1
        }
    }

    for i in 0..<n {
        if possible[i] != 0 {
            answer += 1
        }
    }

    return answer
}

 

코딩테스트 연습 - 체육복