🔗 링크

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

🔢 문제

A 선수가 B 선수보다 실력이 좋다면 A 선수는 B 선수를 항상 이긴다.

선수의 수인 n과 A와 B의 경기 결과가 담긴 2차원 배열 results가 매개변수로 주어진다.

result의 앞 번호는 이긴 선수의 번호, 뒷 번호는 진 선수의 번호로 이루어져있다.

results 배열을 사용하여 순위를 알 수 있는 선수의 수를 구해야한다.

👀 예제로 문제 파악하기

입력 : n 5, results [[4, 3], [4, 2], [3, 2], [1, 2], [2, 5]]

4가 승자, 3이 패자이기 때문에

위 사진과 같이 3이 4보다 순위가 높다.

4가 승자, 2가 패자이기 때문에

순위는 4가 가장 높고, 그 다음으로 3과 2가 있다.

3이 승자, 2가 패자이기 때문에

위 사진과 같이 순위의 순서가 4, 3, 2가 된다.

1이 승자, 2가 패자이기 때문에,

1은 2 앞에 위치하지만 어디에 들어갈지는 알 수 없다. (4번, 3번과의 경기 결과가 없기 때문이다)

2가 승자, 5가 패자이기 때문에

2 뒤에 5가 위치한다.

결과적으로 순위를 알 수 있는 것은 2번과 5번이므로,

2를 리턴한다.

😮 알고리즘 풀이 순서

입력 : n 5, results [[4, 3], [4, 2], [3, 2], [1, 2], [2, 5]]

1) 고유 코드, 이긴 리스트, 진 리스트를 가지고 있는 n개의 객체를 생성한다.
- 이긴 리스트, 진 리스트는 중복을 허용하지 않기 때문에 Set을 사용한다.

2) results의 갯수만큼 결과에 따라 이긴 리스트와 진 리스트에 추가해준다.

3) n개 만큼 반복문을 돌린다.
1. n번째 플레이어가 이긴 기록 리스트에 있는 플레이어가 이긴 사람들은 n번째 사람이 이길 수 있으므로 이긴 기록에 추가해준다.
2. n번째 플레이어가 진 기록 리스트에 있는 플레이어가 진 사람들은 n번째 사람이 이길 수 없으므로 진 기록에 추가해준다.
- node의 최대 depth는 n번이기 때문에 n번만큼 반복

4) 선수의 이긴 기록에 있는 개수와 진 기록에 있는 개수가 n-1과 같다면, 순위를 알 수 있으므로 answer++한다.
5) answer를 리턴한다.

👩‍💻 코드

public class Solution {

  public int solution(int n, int[][] results) {

    int answer = 0;

    ArrayList<Player> players = new ArrayList<>();

    // n 갯수만큼 플레이어 생성 (0번째는 사용X)
    for (int i = 0; i <= n; i++) {
      players.add(new Player(i));
    }

    // 각각 리스트에 결과 삽입
    for (int[] result : results) {
      players.get(result[0]).win.add(result[1]); // 이긴 기록 추가
      players.get(result[1]).lose.add(result[0]); // 진 기록 추가
    }

    for (int depth = 0; depth < n; depth++) { // 한 번 더 depth가 한 번 더 들어갈 수 있기 때문에 n번 반복하게 설정
      for (int i = 1; i <= n; i++) {

        Player player = players.get(i); // 현재 플레이어

        HashSet<Integer> winSet = new HashSet<>(); // 자신이 이긴 플레이어면 그 플레이어가 이긴 사람들도 모두 이김

        for (Integer win : player.win) { // 현재 플레이어가 이길 리스트들
          for (Integer w : players.get(win).win) { // 현재 플레이어가 이긴 플레이어의 이긴 리스트들
            winSet.add(w);
          }
        }
        player.win.addAll(winSet); // 추가

        HashSet<Integer> loseSet = new HashSet<>(); // 자신이 진 플레이어면 그 플레이어가 진 사람들도 모두 짐

        for (Integer lose : player.lose) { // 현재 플레이어가 진 리스트들
          for (Integer l : players.get(lose).lose) { // 현재 플레이어가 진 플레이어의 진 리스트들
            loseSet.add(l);
          }
        }
        player.lose.addAll(loseSet); // 추가
      }
    }

    for (Player player : players) {
      int size = player.win.size() + player.lose.size();

      if (size == n - 1) {
        answer++;
      }
    }
    return answer;
  }

  @Test
  public void 정답() {
    Assert.assertEquals(2, solution(5, new int[][]{{4, 3}, {4, 2}, {3, 2}, {1, 2}, {2, 5}}));
  }


}

class Player {

  int code;

  HashSet<Integer> win = new HashSet<>();
  HashSet<Integer> lose  = new HashSet<>();

  public Player(int code) {
    this.code = code;
  }
}