[Java] 프로그래머스 - 순위

문제링크

코딩테스트 연습 - 순위

문제

주어진 승자와 패자가 있는 배열에서 순위를 결정지을 수 있는 사람이 몇명인지를 구하는 문제입니다.

주어지는 조건은 사람의 수 n 과 승/패 배열입니다.

풀이

주어지는 노드의 개수가 1~N 이므로 간단하게 노드들을 생성해두고, 승리자와 패배자를 연결하여 풀었습니다.

노드의 개수가 100개 이하이고, 배열의 길이가 4500개 이하이므로 시간초과를 크게 고려하지 않아도 될거 같습니다.

다음과 같은 순서로 풀이를 했습니다.

1. 노드들마다 자신이 알고 있는 승자와 패자를 넣음

2. 승자와 패자를 많이 알고 있는 노드 순으로 정렬한 후, 모든 노드를 순회하며, 다시 각각의 승자와 패자를 추가해준다.(이 부분을 빼면 마지막에 순위가 결정되는 경우에 오답이 됩니다.)

3. 다시 그래프를 순회하며, 승자 + 패자의 수가 n - 1 인 노드의 개수를 구합니다.

import java.util.*;

class Solution {
    public int solution(int n, int[][] results) {
        List<Info> graph = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            graph.add(new Info(i));
        }

        for (int[] result : results) {
            int win = result[0] - 1;
            int loose = result[1] - 1;

            Info winnerInfo = graph.get(win);
            Info looserInfo = graph.get(loose);

            winnerInfo.looser.add(loose);
            winnerInfo.looser.addAll(looserInfo.looser);

            looserInfo.winner.add(win);
            looserInfo.winner.addAll(winnerInfo.winner);
        }
        int answer = 0;

        PriorityQueue<Info> queue = new PriorityQueue<>(graph);

        while (!queue.isEmpty()) {
            final Info poll = queue.poll();
            for (Integer i : poll.winner) {
                graph.get(i).looser.addAll(poll.looser);
            }
            for (Integer i : poll.looser) {
                graph.get(i).winner.addAll(poll.winner);
            }
        }

        for (Info info : graph) {
            final int sum = info.winner.size() + info.looser.size();
            if (sum == n - 1) answer++;
        }
        return answer;
    }

    static class Info implements Comparable<Info> {
        int index;
        Set<Integer> winner, looser;

        public Info(int index) {
            this.index = index;
            winner = new HashSet<>();
            looser = new HashSet<>();
        }

        @Override
        public int compareTo(Info o) {
            return Integer.compare(o.winner.size() + o.looser.size(), winner.size() + looser.size());
        }
    }
}

class RankTest {
    @Test
    void solve() {
        Rank r = new Rank();
        final int r1 = r.solution(5, new int[][]{{4, 3}, {4, 2}, {3, 2}, {1, 2}, {2, 5}});
        final int r2 = r.solution(5, new int[][]{{4, 3}, {4, 2}, {3, 2}, {2, 5}, {1, 2}});

        assertEquals(2, r1);
        assertEquals(2, r2);
    }
}

PriorityQueue 를 써서 정렬을 시켰고(사실 처음엔 다른 풀이를 생각해서 큐를 쓰려고 했습니다), 승자와 패자를 저장할 자료구조를 Set 으로 써서 마음껏 add 해도 중복되지 않도록 하였습니다.