프로그래머스 - 순위

programmers.co.kr/learn/courses/30/lessons/49191

코딩테스트 연습 - 순위

1. 유형

그래프

 

2. 풀이

 

 

설계

1) List로 그래프 그리기

2) dfs돌려서 나보다 낮은 애들 값 파악

3) dfs의 리턴값을 이용해서 나보다 순위 높은애들이 몇명이었는지 파악

 

3. 코드

import java.util.*;
class Solution {
    static List<Integer> list[];
    static int rank[];
    static boolean visit[];
    static int max;
    static int dfs(int index){
        int res=0;
        for(int next: list[index]){
            if(!visit[next]){
                visit[next] = true;
                rank[next]++;
                res += dfs(next);
            }
        }
        return res+1;
    }
    public int solution(int n, int[][] results) {
        int answer = 0;
        list = new ArrayList[n+1];
        for(int i=0; i<n+1; i++){
            list[i] = new ArrayList<>();
        }
        for(int i=0; i<results.length; i++){
            int u = results[i][0];
            int v = results[i][1];
            list[u].add(v);
        }
        rank = new int[n+1];
        for(int i=1; i<n+1; i++){
            visit = new boolean[n+1];
            rank[i]+=(dfs(i)-1);
        }
        for(int i=1; i<n+1; i++){
            if(rank[i]==n-1)
                answer++;
        }
        return answer;
    }
}