프로그래머스 순위

https://school.programmers.co.kr/learn/courses/30/lessons/49191

n명의 선수가 있으며, 경기의 결과가 results배열에 주어진다.

주어진 경기 결과로 확실하게 순위를 매길 수 있는 선수의 수를 구하는 문제이다.

예시를 통해 무엇을 구하는지 정확하게 파악해 보자.

n이 5이다 - 선수는 1~5까지 존재한다.

results 배열

1: 승 - [2] 패 - []
2: 승 - [5] 패 - [1, 3, 4]
3: 승 - [2] 패 - [4]
4: 승 - [2,3] 패 - []
5: 승 - [] 패 - [2]

이러한 상황에서, 선수 2는 5에게 이기고 나머지 모두에게 져서 4위이고 선수 5는 2에게만 졌지만 2가 5를 제외한 모두에게 져서 5위이다.

1, 3, 4번 선수는 아직 서로에 대한 대전이 없어 순위가 확실하지 않다.

따라서 2를 반환한다.

처음 봤을때 어렵게생겼네? 라고 느꼈던 문제이다.

문제를 풀 때 쓰인 가장 중요한 개념은 "확실하게 순위를 알 수 있는 선수"이다.

어떤 선수의 순위가 확실하게 정해지는 경우가 언제인가?를 생각하니 실마리를 알게 되었다.

임의의 선수 A에 대해서

1. A가 직접 이기거나 A에게 진 선수가 이긴 선수들은 A가 이긴다.

2. A가 직접 지거나, A에게 이긴 선수를 이긴 선수는 A가 못이긴다.

3. 1번과 2번 과정을 모두 진행한 뒤, 이길 선수 + 질 선수의 값이 A를 제외한 n-1인 경우 순서가 정해진다.

위 경우를 예로 들며 풀이 방법을 소개하겠다.

1: 승 - [2] 패 - []
2: 승 - [5] 패 - [1, 3, 4]
3: 승 - [2] 패 - [4]
4: 승 - [2,3] 패 - []
5: 승 - [] 패 - [2]

위처럼 정해진 경우에,

1번
2번을 직접 이기며, 2번이 5번을 이김.
승: [2, 5], 패: []

2번
5번을 직접 이기지만 1, 3, 4번에게 패배함. 5번이 이기는 선수가 없음.
1, 3, 4번에게 지고 선수는 1, 4는 지는 선수가 없으며 3번은 4번에게 패배함.
승: [5], 패: [1, 3, 4]

3번
2번을 직접 이기며 2번이 5번을 이김.
4번에게 지며, 4번은 지는 선수가 없음.
승: [2, 5], 패: [4]

4번
2번과 3번을 직접 이기며 2번은 5번을 이김.
승: [2, 3, 5], 패: []

5번
2번에게 지고, 2번 선수는 1, 3, 4번 선수에게 지며 3번은 4번 선수에게 짐.
승: [], 패: [1, 2, 3, 4]

따라서 결과 배열은

1: 승 - [2, 5] 패 - []
2: 승 - [5] 패 - [1,3,4]
3: 승 - [2, 5] 패 - [4]
4: 승 - [2, 3, 5] 패 - []
5: 승 - [] 패 - [1, 2, 3, 4]

그리고 2번, 5번의 승리 선수 + 패배 선수의 합이 n-1 = 4이므로 2번과 5번은 순위가 정해짐.

class Solution {
    fun solution(n: Int, results: Array<IntArray>): Int {
        val persons = Array(n + 1){Person()}

        for(result in results){
            persons[result[0]].win.add(result[1])
            persons[result[1]].lose.add(result[0])
        }

        var answer = 0
        for(i in 1..n){
            val win = mutableListOf<Int>()
            val lose = mutableListOf<Int>()

            winDfs(i, persons, win, BooleanArray(n + 1){false})
            loseDfs(i, persons, lose, BooleanArray(n + 1){false})
            if(win.size + lose.size == n - 1) answer++
        }

        return answer
    }

    fun winDfs(start: Int, persons: Array<Person>, winList: MutableList<Int>, check: BooleanArray){
        val curPerson = persons[start]
        check[start] = true
        curPerson.win.forEach {
            if(!check[it]) {
                winList.add(it)
                winDfs(it, persons, winList, check)
            }
        }
    }

    fun loseDfs(start: Int, persons: Array<Person>, loseList: MutableList<Int>, check: BooleanArray){
        val curPerson = persons[start]
        check[start] = true
        curPerson.lose.forEach {
            if(!check[it]) {
                loseList.add(it)
                loseDfs(it, persons, loseList, check)
            }
        }
    }
}

data class Person(
    val win: MutableList<Int> = mutableListOf(),
    val lose: MutableList<Int> = mutableListOf(),
)

선수를 Person으로 두고, 해당 선수가 이기는 선수 지는 선수를 mutableList로 선언.

1번부터 n번까지 각 선수에 대해 dfs로 i번째 선수가 이길 만한 선수, 질 만한 선수들의 번호를 모은다.

두 배열의 크기 합이 n-1이면 answer을 1 더함.