[알고리즘] Programmers - 순위

프로그래머스

문제 설명

• 선수의 수는 1명 이상 100명 이하이다.
• 경기 결과는 1개 이상 4,500개 이하이다.
• 경기 결과를 나타내는 리스트가 주어지는데, 이를 통해 순위를 정확하게 파악할 수 있는 선수들의 수를 반환해야 한다.
• 모든 경기 결과에는 모순이 없다.

문제 해결

• 승 여부를 확인할 수 있는 "승 그래프"와 패 여부를 확인할 수 있는 "패 그래프", 총 2개의 그래프를 구성했다.
• 2개의 그래프를 dfs 탐색하며 자신보다 쎈 선수들과 약한 선수들을 파악한다.
• dfs 탐색을 통해 방문할 수 없는 정점(선수)이 있는 경우 정확하게 파악할 수 없기 때문에 answer를 증가시키지 않는다.

시간 복잡도

• O(N)

풀이 코드

import java.util.*;

class Solution {
    static List<List<Integer>> winGraph, loseGraph;
    static boolean[] v;
    
    public int solution(int n, int[][] results) {
        int answer = 0;
        
        winGraph = new ArrayList<>();
        loseGraph = new ArrayList<>();
        for (int i = 0; i <= n; i++) {
            winGraph.add(new ArrayList<>());
            loseGraph.add(new ArrayList<>());
        }
        
        for (int[] result : results) {
            int a = result[0];
            int b = result[1];
            winGraph.get(a).add(b);
            loseGraph.get(b).add(a);
        }
        
        for (int now = 1; now <= n; now++) {
            v = new boolean[n + 1];
            v[now] = true;
            dfs(now, winGraph);
            dfs(now, loseGraph);
            
            for (int i = 1; i <= n; i++) {
                if (!v[i]) break;
                if (i == n) {
                    answer++;
                }
            }
        }
        
        return answer;
    }
    
    static void dfs(int now, List<List<Integer>> graph) {
        for (int next : graph.get(now)) {
            if (v[next]) continue;
            v[next] = true;
            dfs(next, graph);
        }
    }
    
}

결과

---

1차 시도

1. 풀이 코드

import java.util.*;

class Solution {
    static List<List<Integer>> winGraph, loseGraph;
    static boolean[] v;
    
    public int solution(int n, int[][] results) {
        int answer = 0;
        
        winGraph = new ArrayList<>();
        loseGraph = new ArrayList<>();
        for (int i = 0; i <= n; i++) {
            winGraph.add(new ArrayList<>());
            loseGraph.add(new ArrayList<>());
        }
        
        for (int[] result : results) {
            int a = result[0];
            int b = result[1];
            winGraph.get(a).add(b);
            loseGraph.get(b).add(a);
        }
        
        for (int now = 1; now <= n; now++) {
            v = new boolean[n + 1];
            v[now] = true;
            dfs(now, winGraph);
            dfs(now, loseGraph);
            
            for (int i = 1; i <= n; i++) {
                if (!v[i]) break;
                if (i == n) {
                    answer++;
                }
            }
        }
        
        return answer;
    }
    
    static void dfs(int now, List<List<Integer>> graph) {
        for (int next : graph.get(now)) {
            if (v[next]) continue;
            v[next] = true;
            dfs(next, graph);
        }
    }
    
}

2. 문제점

• 승 그래프, 패 그래프 총 2개의 그래프를 탐색하는 2번의 dfs로 인해 시간 복잡도가 증가하는 문제점이 발생했다.
• 두 개의 그래프를 그리기 때문에 메모리 측면에서도 공간을 더 차지하는 문제점이 있다.

3. 결과

---

2차 시도

1. 풀이코드

import java.util.*;

class Solution {
    public int solution(int n, int[][] results) {
        int answer = n;
        int INF = n * n;
        int[][] graph = new int[n + 1][n + 1];
        
        for (int i = 1; i <= n; i++) {
            Arrays.fill(graph[i], INF);
            graph[i][i] = 0;
        }
        
        for (int[] result : results) {
            int a = result[0];
            int b = result[1];
            graph[a][b] = 1;
        }
        
        for (int k = 1; k <= n; k++) {
            for (int i = 1; i <= n; i++) {
                for (int j = 1; j <= n; j++) {
                    graph[i][j] = Math.min(graph[i][j], graph[i][k] + graph[k][j]);
                }
            }
        }
        
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                if (i == j) continue;
                
                if (graph[i][j] == INF && graph[j][i] == INF) {
                    answer--;
                    break;
                }
            }
        }
        
        return answer;
    }
}

2. 1차 시도 코드 개선점

• 플로이드 와샬 알고리즘을 적용하여 모든 정점을 탐색할 수 있는지 확인하는 로직으로 구성했다.
• 1차 시도 방법과 비교했을 때, 시간과 메모리 측면에서 1차 시도 방법이 더 효율적인 것을 볼 수 있다.
• 플로이드 와샬 방법보다는 dfs를 2번 수행하는 방식이 더 효율적이다.

3. 결과