프로그래머스 탐욕법 섬연결하기

fun solution2(n: Int, costs: Array<IntArray>): Int {

    var answer = 0
    var costsArray = costs.toMutableList()
    var container = mutableListOf<Int>()
    container.add(0)
    var count = 0
    while (count<n-1){
        var pair = 0 to -1
        for (i in costsArray){
            val test =i.containWj(container)
            if (test.first){ // 사용해도됨
                if(pair.second ==-1){ // 최초사용
                    pair = test.second to i[2] // 초기화
                }else {
                    if (pair.second > i[2]) {
                        pair = test.second to i[2] // 바까줌
                    }
                }
            }
        }
        container.add(pair.first)
        answer += pair.second
        count ++
    }

    println(answer)


    return answer
}

fun IntArray.containWj(container : MutableList<Int>): Pair<Boolean, Int> {
    var count = 0
    var number = 0
    var other = 0
    for(i in container){
        if(this.contains(i)) {
            count++
            number =i
        }
        if(count ==2){
            break
        }
    }
    if( this[0] == number){
        other = this[1]
    }else{
        other = this[0]
    }

    return if( count !=2 && count!=0 ) true to other else false to other


}

확장함수를 써봣다는거에 만족...

다른 사람들 풀이가 너무 간단해서 좀 그럼..

 

일단 나는 최초 0번부터 시작해서

1) 0과 연결될 수 있는 것중 가장 코스트가 낮은거 a를 선택

2) 0과 a를 하나의 섬으로 만들어서 0 a 와의 연결 될 수 있는 다리중 가장 코스트 낮은 b 선택

3) 0 a b 를 하나의 섬으로 해서 ... 

    이때 다리가 연결된 섬 끼리 연결 되어있거나 가장 큰 섬을 포함하지 않으면 제외하는 확장함수 만듬

 

fun solution(n: Int, costs: Array<IntArray>): Int {
        var cost = 0
        val sortedCosts = costs.sortedBy { it[2] }
        val visitedIslands = HashSet<Int>()
        var builtBridgeCount = 0

        while(builtBridgeCount != n - 1) {
            if(builtBridgeCount != 0) {
                val nextBridge = sortedCosts.first {
                    visitedIslands.contains(it[0]) && !visitedIslands.contains(it[1])
                    || visitedIslands.contains(it[1]) && !visitedIslands.contains(it[0])
                }
                cost += nextBridge[2]
                visitedIslands.add(nextBridge[0])
                visitedIslands.add(nextBridge[1])
                builtBridgeCount++
            } else {
                val firstBridge = sortedCosts.first()
                cost = firstBridge[2]
                visitedIslands.add(firstBridge[0])
                visitedIslands.add(firstBridge[1])
                builtBridgeCount++
            }
        }
        return cost
    }

이 풀이는 가격이 낮은 순으로 정렬해서 풀었더라 이것도 괜찮은듯.