[LeetCode] 2924. Find Champion II

[문제 링크]

https://leetcode.com/problems/find-champion-ii/description/

 

[문제]

0부터 N-1까지 번호가 매겨져 있습니다. 일부 선수들은 서로 경기했으며, 그 결과가 edges 배열에 이긴 선수 → 진 선수 형태로 주어집니다.

예를 들어, edges[i] = [winner, loser]는 winner 선수가 loser 선수를 이겼음을 의미합니다.

**챔피언(Champion)**이란, 어떤 선수도 챔피언을 이기지 못한 선수를 의미합니다. 즉, 챔피언은 진입 차수(In-degree)가 0인 노드입니다.

단, 챔피언이 여러 명이면 -1을 반환해야 합니다. 유일한 챔피언이 존재하면 해당 챔피언의 번호를 반환하세요. 챔피언이 없으면 -1을 반환하세요.

[풀이 과정]

간선의 개수로 구하는 생각을 하기까지가 오래 걸렸지 구현은 어렵지 않았습니다.

간선의 개수로 구한다는 말의 뜻은 본인의 노드가 챔피언이면 자신을 가르키는 선은 없어야 합니다.

주의사항으론 자신을 가리키는 선이 없는 노드가 두개 이상이어도 -1을 반환하는 것입니다.

 

[코드]

class Solution {
    public int findChampion(int n, int[][] edges) {
        int[] inDegree = new int[n]; // 진입 차수를 저장할 배열

        for(int[] edge : edges) { // 패자 간선 증가
            int loser = edge[1];
            inDegree[loser]++;
        }

        int champion = -1;

	// 챔피언이 두개면 -1;
        for(int i = 0; i < n; i++) {
            if(inDegree[i] == 0) {
                if(champion == -1) {
                    champion = i;
                } else {
                    return -1;
                }
            } 
        }

        return champion;
    }
}

[회고]

생각보다 쉬웠습니다.

 

 

 

 

질문과 피드백은 언제나 환영입니다.

감사합니다.