[Programmers] 순위

본 게시글은 PC 환경에서 보기 편하도록 설정이 되어 있습니다.

순위

그래프 로 분류되어있는 완전탐색류 문제입니다.

저는 모든 경기수를 확인하기 위해 DFS를 이용하여 문제를 풀었습니다.

 

풀이 스타일

Java와 같은 객체지향 언어를 이용하여 알고리즘을 푼다면 객체지향스럽게 알고리즘을 풀어야 한다고 생각합니다.

단순한 알고리즘 풀이는 가독성은 당연히 떨어지고, Java를 쓰는 이유가 퇴색되는 것 같습니다.

따라서, Java를 이용해서 문제를 푸신다면 객체가 해야할 행동으로 문제를 풀 수 있도록 하시는 것을 추천드립니다.

모든 선수를 Boxer로, Boxer를 List로 전부 들고있는 일급컬렉션인 MatchHistory를 생성수

Boxer가 이길수 있는 모든 Boxer와

Boxer가 질수 밖에 없는 모든 Boxer를 Set을 이용하여 구한후

Set의 size()를 통해 문제를 풀었습니다.

코드에 주석을 첨부하였으니 이해하기에 무리가 없을것 같습니다.

코드

import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;
 
public class Main {
 
    public static void main(String[] args) {
        Solution solution = new Solution();
        System.out.println(solution.solution(5, new int[][]{{4, 3}, {4, 2}, {3, 2}, {1, 2}, {2, 5}}) == 2);
        System.out.println(solution.solution(5, new int[][]{{4, 5}, {3, 5}, {3, 4}, {2, 3}, {1, 2}}) == 5);
        System.out.println(solution.solution(5, new int[][]{{1, 2}, {2, 3}, {1, 3}, {4, 5}, {3, 5}}) == 1);
    }
}
 
class Solution {
    public int solution(int n, int[][] results) {
        int answer = 0;
 
        List<Boxer> boxers = new ArrayList<>();
 
        for (int i = 1; i <= n; i++) {
            Boxer boxer = new Boxer(i);
            boxers.add(boxer);
        }
 
        MatchHistory matchHistory = new MatchHistory(boxers);
 
        for (int[] result : results) {
            int winner = result[0];
            int loser = result[1];
            matchHistory.addHistory(winner, loser);
        }
 
        answer = matchHistory.getAllMatchBoxer(n);
 
        return answer;
    }
}
 
class Boxer {
    private int number;
    private Set<Boxer> weak = new HashSet<>(); // 내가 이긴 애들 == 약한애들
    private Set<Boxer> strong = new HashSet<>(); // 내가 진 애들 == 강한애들
 
    public Boxer(int number) {
        this.number = number;
    }
 
    public int getMatchCount() {
        Set<Boxer> loseMatch = new HashSet<>(); // 나보다 강한애들을 적어둘 곳
        Set<Boxer> winMatch = new HashSet<>(); // 나보다 약한애들을 적어둘 곳
        makeLoseMatch(this, loseMatch);
        makeWinMatch(this, winMatch);
        return loseMatch.size() + winMatch.size();
    }
 
    private void makeLoseMatch(Boxer boxer, Set<Boxer> loseMatch) {
        for (Boxer stronger : boxer.strong) { // 나보다 강한애들중에
            if (loseMatch.contains(stronger)) { // 이미 강한애 목록에 있는애는 건너뛰고
                continue;
            }
            makeLoseMatch(stronger, loseMatch); // 목록에 없는 없으면 이 사람보다 강한사람들을 나보다 강한목록에 추가하러 가자
        }
        loseMatch.addAll(boxer.strong); // 나보다 강한 사람들은 전부 목록에 추가하자
    }
 
    private void makeWinMatch(Boxer boxer, Set<Boxer> winMatch) {
        for (Boxer weaker : boxer.weak) {
            if (winMatch.contains(weaker)) {
                continue;
            }
            makeWinMatch(weaker, winMatch);
        }
        winMatch.addAll(boxer.weak);
    }
 
    public void win(Boxer boxer) { // 내가 이겼다
        weak.add(boxer);// 나보다 약하다
    }
 
    public void lose(Boxer boxer) { // 내가 졌다
        strong.add(boxer); // 나보다 강하다
    }
 
    public int getNumber() {
        return this.number;
    }
}
 
class MatchHistory {
 
    List<Boxer> boxers;
 
    public MatchHistory(List<Boxer> boxers) {
        this.boxers = boxers;
    }
 
    public int getAllMatchBoxer(int n) {
        return (int) boxers.stream()
                .filter(boxer -> boxer.getMatchCount() == n - 1)
                .count();
    }
 
    public void addHistory(int winnerNumber, int loserNumber) {
        Boxer winner = null;
        Boxer loser = null;
        for (Boxer boxer : boxers) {
            winner = findBoxer(winnerNumber, winner, boxer);
            loser = findBoxer(loserNumber, loser, boxer);
        }
        if (winner != null && loser != null) {
            winner.win(loser);
            loser.lose(winner);
        }
    }
 
    private Boxer findBoxer(int number, Boxer boxer, Boxer someBoxer) {
        if (someBoxer.getNumber() == number) {
            return someBoxer;
        }
        return boxer;
    }
 
}