[이코테] 그리디 알고리즘 - 모험가 길드 코틀린 코드

 

우선 필자가 처음에 작성한 틀린 코드를 공개한다.

 

fun main() {

    var n = 5
    val member = mutableListOf(1,2, 4,3,1)

    member.sort() 
    
    var cnt = 0
    while(n > 0) {

        if (member[n - 1] < n) {
            for (i in 0..<member[n-1]-1) {
                n -= 1
                member.removeFirst()
            }
            n -= 1
            member.removeLast()
            cnt += 1
        } else if (member[n - 1] == n) {
            n = 0
            cnt += 1
        } else { // member[n-1]= > n
            n = 0
        }
    }
    println("cnt = " + cnt)
}

 

정리되지 않은 코드이기도 하고 로직자체도 억지로 끼워맞춘 느낌인데 공개하는 이유는

여기서 필자가 착각한 부분이 '공포도가 높은 모험가'에게 집착했다는 것이다.

'공포도가 X인 모험가는 반드시 X명 이상으로 구성한 모험가 그룹에 참야해야한다.' 는 문제를 읽고 

'아..! 공포도 X가 큰 걸 잘 처리하는 게 핵심이구나..!' 하고 낚인(?) 것이다.

실제로 이렇게 이해하고는 문제 하단 조건인

'또한 몇 명의 모험가는 마을에 그대로 남아 있어도 되기 때문에, 모든 모험가를 특저한 그룹에 넣을 필요는 없습니다.'

이 조건의 의미를 제대로 파악하지 못했다.

모든 문제의 조건은 꼼꼼히 읽고 이해해야함을 깨달았다.

 

 

결국 이 문제의 핵심은 조를 많이 짜는 것이기 때문에

적은 인원으로 조를 짜야 한다.

 

필자의 경우 처음 예시인 2,3,1,2,2의 경우에

가장 큰 공포도인 '3'에 집착해 3명이 한조를 만드는 것에 집착했다.

문제에서도 1,2,3인 조와, 2,2인 조를 만들 수 있다고 해서

'3'을 중점으로 공포도가 낮은 1,2를 한 조로,

남은 멤버 (각각 공포도 2)들을 다시 위의 로직으로 계산해 하나의 조를 추가로 생성하는 로직을 구현했다.

 

아래의 테스트 케이스에서 이 접근법이 틀렸음을 발견했고, 

로직을 다시 생각해 코드를 다시 작성했다.

 

실패한 테스트 케이스 : 1,1,2,3,4

위의 테스트 코드로 실행하면 정답인 2가 아닌, 1이 나온다.

 

새로 작성한 로직

fun main() {

    var n = 5
    val member = mutableListOf(2,3,1,2,2)

    member.sort() // 1,2,2,2,3

    var answer = 0
    var groupMember = 0
    for (i in member) { // i=1 /
        groupMember += 1
        if(groupMember >= i) {
            answer += 1
            groupMember = 0
        }
    }

    println("answer = $answer")
}

 

 

결국 이 문제의 핵심은 다음과 같다.

1. 공포도가 낮은 사람부터 그룹을 결정해야 한다.

    => 때문에 정렬이 필요하다.

2. 현재 그룹원 수가 현재 공포도 이상일 때 그룹을 결정해야 한다.

 

주의할 점은 다음과 같다.

1. 그룹원이 증가하는 방식이 일관되어야 한다.

    groupMember += 1 은 무조건 실행되어야 한다. (현재 모험가를 포함하는 과정이기 때문)

2. 공포도가 높은 사람을 먼저 처리하면 안된다.

    공포도 3인 사람이 먼저 그룹을 만들려면 최소 3명이 필요하므로, 

    공포도 1,2인 사람을 먼저 배치하면 더 작은 그룹을 여러 개 만들 수 있다

 

즉, 낮은 공포도부터 처리하기 위해 정렬을 수행하고, 현재 그룹원의 수와 공포도를 비교해(count > 공포도)

최대한 많은 그룹을 만들 수 있도록 전략적으로 그룹을 결성해야한다.