[알고리즘] 프로그래머스 순위 -그래프, 플로이드 워셜- 자바 코틀린

 

 

programmers.co.kr/learn/courses/30/lessons/49191?language=kotlin

코딩테스트 연습 - 순위

 

프로그래머스 LV 3 문제 순위를 풀어보았습니다. ㅎㅎ

 

권투 선수간 누가 누굴 이겼는지 알 수 있는 배열이 주어지는데 이걸 토대로 몇명의 권투 선수 순위를 확정지을 수 있는지 구하는 문제였습니다. 

 

이전에 백준에서 풀었던 저울이라는 문제와 비슷했고 똑같이 N:N의 관계를 파악하기 위해 플로이드 워셜 알고리즘을 사용해서 풀었습니다.

youngest-programming.tistory.com/535?category=1013047

[알고리즘] 백준 10159 저울 -플로이드 워셜- 자바 코틀린

 

풀이는 주석으로 적어놨습니다. 감사합니다. 

 

[Java]

class Solution {
    private lateinit var weights: Array<IntArray>
    fun solution(n: Int, results: Array<IntArray>): Int {
        var answer = 0
        weights = Array(n + 1) { IntArray(n + 1) }
        for (i in results.indices) {
            val win = results[i][0]
            val lose = results[i][1]
            weights[win][lose] = 1 //이김
            weights[lose][win] = -1 //짐
        }
        floyd(n)
        for (i in 1..n) {
            var cnt = 0
            for (j in 1..n) {
                if ((weights[i][j] != 0 || weights[j][i] != 0) && i != j) { // 해당 선수가 타 선수와의 승패를 아는 경우
                    cnt++
                }
            }
            if (cnt == n - 1) answer++ // 자신을 제외한 타선수와의 승패결과를 모두 아는 경우 순위확정 + 1
        }
        println(answer)
        return answer
    }

    private fun floyd(n: Int) {
        for (k in 1..n) {
            for (i in 1..n) {
                for (j in 1..n) {
                    if (weights[i][k] == weights[k][j] && weights[i][k] != 0) { //서로 비교할 수 있는 경우
                        weights[i][j] = weights[i][k] // i>k>j OR i<k<j 이므로 i,k 의 대소관계도 알 수 있게된다.
                    }
                }
            }
        }
    }
}

 

 

[Kotlin]

class Solution {
    private lateinit var weights: Array<IntArray>
    fun solution(n: Int, results: Array<IntArray>): Int {
        var answer = 0
        weights = Array(n + 1) { IntArray(n + 1) }
        for (i in results.indices) {
            val win = results[i][0]
            val lose = results[i][1]
            weights[win][lose] = 1 //이김
            weights[lose][win] = -1 //짐
        }
        floyd(n)
        for (i in 1..n) {
            var cnt = 0
            for (j in 1..n) {
                if ((weights[i][j] != 0 || weights[j][i] != 0) && i != j) { // 해당 선수가 타 선수와의 승패를 아는 경우
                    cnt++
                }
            }
            if (cnt == n - 1) answer++ // 자신을 제외한 타선수와의 승패결과를 모두 아는 경우 순위확정 + 1
        }
        println(answer)
        return answer
    }

    private fun floyd(n: Int) {
        for (k in 1..n) {
            for (i in 1..n) {
                for (j in 1..n) {
                    if (weights[i][k] == weights[k][j] && weights[i][k] != 0) { //서로 비교할 수 있는 경우
                        weights[i][j] = weights[i][k] // i>k>j OR i<k<j 이므로 i,k 의 대소관계도 알 수 있게된다.
                    }
                }
            }
        }
    }
}

 

 

github.com/mtjin/algorithm_practice/tree/master/%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%A8%B8%EC%8A%A4%20%EC%88%9C%EC%9C%84%20-%EA%B7%B8%EB%9E%98%ED%94%84%2C%20%ED%94%8C%EB%A1%9C%EC%9D%B4%EB%93%9C%20%EC%9B%8C%EC%85%9C-

mtjin/algorithm_practice

 

 

댓글과 공감은 큰 힘이 됩니다. 감사합니다. !!