[프로그래머스 / Level3] 순위 (Java)

문제 보기

사용한 것

• 순서가 없고 중복을 허용하지 않는 자료구조 Set

풀이 방법

• Result 클래스에 Set으로 win, lose 필드 생성
• Map<Integer, Result> 로 선수 별 결과를 저장
• A가 B를 이기면
  • A win에 B, B win 추가
  • B lose에 A, A lose 추가
  • A lose들을 돌면서 B, B win 추가
  • B lose들을 돌면서 A, A lose 추가
• win, lose 크기의 합이 n - 1이면 순위가 정해진 것

코드

class Solution {

    public int solution(int n, int[][] results) {
        Map<Integer, Result> map = new HashMap<>();
        for (int[] result : results) {
            int winner = result[0];
            int loser = result[1];

            if (!map.containsKey(winner)) {
                map.put(winner, new Result());
            }
            if (!map.containsKey(loser)) {
                map.put(loser, new Result());
            }

            Result winnerResult = map.get(winner);
            Result loserResult = map.get(loser);
            for (Integer winnersWinner : winnerResult.lose) {
                Result winnersWinnerResult = map.get(winnersWinner);
                winnersWinnerResult.win.addAll(loserResult.win);
                winnersWinnerResult.win.add(loser);
            }
            winnerResult.win.addAll(loserResult.win);
            winnerResult.win.add(loser);

            for (Integer losersLoser : loserResult.win) {
                Result losersLoserResult = map.get(losersLoser);
                losersLoserResult.lose.addAll(winnerResult.lose);
                losersLoserResult.lose.add(winner);
            }
            loserResult.lose.addAll(winnerResult.lose);
            loserResult.lose.add(winner);
        }

        int answer = 0;
        for (Integer key : map.keySet()) {
            Result result = map.get(key);
            if (result.win.size() + result.lose.size() == n - 1) {
                answer++;
            }
        }

        return answer;
    }
}

class Result {

    public Set<Integer> win = new HashSet<>();

    public Set<Integer> lose = new HashSet<>();
}