프로그래머스: 순위 [JAVA]

문제 링크

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

코딩테스트 연습 - 순위

풀이

 문제에서 요구하는 정확하게 순위를 매길 수 있는 선수는 이 선수를 이길 수 있는 승자와 이 선수에게 지는 패자의 명수 합이 n - 1이 되어야 한다. 또한 문제 요구 상 선수 a를 이긴 선수 b가, 만약 선수 c에게는 진다면 선수 a는 선수 c에게 무조건 지는 상태가 된다. 결국 선수 a를 이기는 선수들의 목록이 조건 상으로는 직접 연결이 아닌 선수 b를 통해 간접적으로 연결되기 때문에, 이를 찾기 위해선 그래프 탐색이 요구된다.

 이를 해결하기 위해 처음에 경기 결과를 담은 2차원 배열 results를 각 선수들의 번호를 인덱스로 삼은 배열 2개(해당 선수를 상대로 이기거나 진)에 이를 담는다. 이후 각 선수들을 상대로 승자와 패자의 수를 구하는 각각의 dfs 탐색을 돌린다. 이때 선수들을 방문하면 HastSet에 해당 선수들을 저장하고 탐색을 이어가고, 중복 선수 방문을 방지하고자 방문 배열을 활용하여 탐색하면 시간을 훨씬 줄일 수 있다. 이후에는 승자, 패자 선수들을 담은 HashSet의 사이즈 합이 n-1이라면 답을 하나 추가하면 된다.

 

class Solution {

        ArrayList<Integer> isWin[], isLose[];//승패 관계 저장 ArrayList
        HashSet<Integer> winnerSet, loserSet; //순위 파악용 HashSet
        boolean winnerVisited[], loserVisited[]; //dfs 방문 체크 배열

        public int solution(int n, int[][] results) {
            int answer = 0;
            //배열 초기화
            isWin = new ArrayList[n + 1];
            isLose = new ArrayList[n + 1];

            for (int i = 0; i <= n; i++) {
                isWin[i] = new ArrayList<>();
                isLose[i] = new ArrayList<>();
            }
            //승패 관계 저장 (양방향)
            for (int i = 0; i < results.length; i++) {
                int winner = results[i][0], loser = results[i][1];
                isWin[winner].add(loser);
                isLose[loser].add(winner);
            }

            for (int i = 1; i <= n; i++) {//각 선수에 대해 승자, 패자를 구해서 순위 파악
                winnerSet = new HashSet<>();
                loserSet = new HashSet<>();
                winnerVisited = new boolean[n + 1];
                loserVisited = new boolean[n + 1];

                checkWinner(i);
                checkLoser(i);
                
                //양쪽 합해 정확히 n-1이면 순위 파악 가능
                if (winnerSet.size() + loserSet.size() == n - 1)
                    ++answer;
            }
            
            return answer;
        }

        public void checkWinner(int player) {//dfs 기반 승자 탐색
            for (Integer winner : isLose[player]) {
                if (winnerVisited[winner] == false) {
                    winnerSet.add(winner);
                    winnerVisited[winner] = true;
                    checkWinner(winner);
                }
            }
        }

        public void checkLoser(int player) {//dfs 기반 패자 탐색
            for (Integer loser : isWin[player]) {
                if (loserVisited[loser] == false) {
                    loserSet.add(loser);
                    loserVisited[loser] = true;
                    checkLoser(loser);
                }
            }
        }
    }

결과