[Swift 알고리즘/Greedy] Grouping children 알고리즘

Grouping children 문제:

Organize them into the minimum possible number of groups such that the age of any two children in the same group differ by at most one year.

교실에 있는 아이들을 1살 차이나도록 묶는데, 그 소그룹의 숫자가 가장 저게 나오는 방법을 찾는것이다. 

• 아이들의 수 : n
• C = {child1, child2, child3, child4 ... childn}
• a(i) = child i의 나이
• groups를 찾는 것이다. G1, G2, G3 ,,, Gk, C = G1 ∪ G2 ∪ G3 ∪ ... ∪ Gk

Greedy 알고리즘으로 문제풀이

Greedy 알고리즘으로 문제푸는이유 : 

아이들 중에 가장 나이가 작은 친구를 first라도 둔다면, first의 나이 + 1를 넘지 않는 가장 나이가 많은 친구까지를 찾아서 하나의 그룹에 넣는다. 그리고 그다음으로 나이가 많은 친구를 새로운 first로 둔다. (그리디 해결법의 큰 문제를 작은 문제로 나눠서 푸는 것이다.) 그리고 마찬가지로 first 로부터 1년 이내의 아이들을 다 찾아서 새로운 그룹에 넣는다. 이렇게 하면 매 상황에 최적의 해로 문제를 푸는 방식이다.

즉, 가장 왼쪽의 친구를 찾는다면, 그 친구 왼쪽에는 아무도 없기 때문에, 그친구를 고르고 1년 이내의 친구까지 찾아낸다. 그리고 마지막 친구 다음친구를 또 가장 왼쪽의 친구로 둔다. 처음에 골랐던 친구들은 고려하지않는다. 이렇게되면, 모든 child들을 고려하면서 최적값을 구할 수 있다.

runnig time : NlogN

var n = 10
var children = ["c1":3.5, "c2": 4.5, "c3": 6, "c4":7, "c5":3.4, "c6":5.6, "c7":7.8, "c8":9, "c9":8.8, "c10":2.6]
var groups = [Int: [String]]()
let sortedChildren = children.sorted(by: {$0.1 < $1.1})

var first = sortedChildren[0].1
var index = 1
var group = [String]()
for child in sortedChildren {
    if first+1 >= child.1 && child.1 >= first {
        group.append(child.0)
    } else{
        first = child.1
        groups.updateValue(group, forKey: index)
        index += 1
        group.removeAll()
        group.append(child.0)
    }
}
groups.updateValue(group, forKey: index)

print(groups)