[프로그래머스] 탐욕법(Greedy) - 체육복 (Swift 풀이)

programmers.co.kr/learn/courses/30/lessons/42862

코딩테스트 연습 - 체육복

학생들이 가지고 있는 체육복의 개수를 저장하는 배열 students

일단 모든 학생이 기본적으로 1벌의 체육복을 가지고 있으므로 1을 n번 반복하여 저장한다.

var students = [Int](repeating: 1, count: n)

 

잃어버린 사람은 체육복을 1벌 빼고, 여벌을 가져온 사람은 체육복을 1벌 증가시킨다.

여기서, lost 배열과 reserve의 값은 몇번째 학생인지를 나타내는 것이므로, 배열의 인덱스값으로 넣기 위해서는 -1을 해주어야 한다.

// 잃어버린 사람은 체육복 0벌
for l in lost {
    students[l-1] = 0
}
// 여벌 가져 온 사람은 +1 벌
for r in reserve {
    students[r-1] += 1
}

 

이제 students 배열을 탐색하면서, 체육복이 0벌인 학생을 발견하면 앞, 또는 뒤의 학생이 체육복을 2벌 이상 가지고 있으면 빌리도록 한다.

앞 뒤 학생 모두에게 빌리지 못하면, 빌리지 못한 학생 count를 1 증가시킨다.

var count = 0 // 체육복을 빌리지 못한 학생 수
for i in 0..<n {
    if students[i] == 0 {
        if i>0 && students[i-1] > 1 {
            // 앞번호 학생에게 빌린다.
            students[i] = 1
            students[i-1] = 1
        } else if i<n-1 && students[i+1] > 1 {
            // 뒷번호 학생에게 빌린다.
            students[i] = 1
            students[i+1] = 1
        } else {
            // 빌리지 못했다.
            count += 1
        }
    }
}

최종적으로, 전체 학생 수 n에서 count 를 뺀 값을 반환한다.

 

최종 코드

import Foundation

func solution(_ n:Int, _ lost:[Int], _ reserve:[Int]) -> Int {

    // 가지고 있는 체육복 개수 저장 (기본적으로 1벌)
    var students = [Int](repeating: 1, count: n)
    
    // 잃어버린 사람은 체육복 0벌
    for l in lost {
        students[l-1] = 0
    }
    // 여벌 가져 온 사람은 +1 벌
    for r in reserve {
        students[r-1] += 1
    }
    
    var count = 0 // 체육복을 빌리지 못한 학생 수
    for i in 0..<n {
        if students[i] == 0 {
            if i>0 && students[i-1] > 1 {
                // 앞번호 학생에게 빌린다.
                students[i] = 1
                students[i-1] = 1
            } else if i<n-1 && students[i+1] > 1 {
                // 뒷번호 학생에게 빌린다.
                students[i] = 1
                students[i+1] = 1
            } else {
                // 빌리지 못했다.
                count += 1
            }
        }
    }
    
    return n - count
}