[프로그래머스] 프로그래머스 Level 3 순위 풀이 코드

프로그래머스 Level 3 순위 풀이 코드

---

인터넷에 통과할 수 있는 코드가 없길래 써보는 코드

문제

---

n명의 권투선수가 권투 대회에 참여했고 각각 1번부터 n번까지 번호를 받았습니다. 권투 경기는 1대1 방식으로 진행이 되고, 만약 A 선수가 B 선수보다 실력이 좋다면 A 선수는 B 선수를 항상 이깁니다. 심판은 주어진 경기 결과를 가지고 선수들의 순위를 매기려 합니다. 하지만 몇몇 경기 결과를 분실하여 정확하게 순위를 매길 수 없습니다.

선수의 수 n, 경기 결과를 담은 2차원 배열 results가 매개변수로 주어질 때 정확하게 순위를 매길 수 있는 선수의 수를 return 하도록 solution 함수를 작성해주세요.

입출력 예시

---

n: 5
results: {{4, 3}, {4, 2}, {3, 2}, {1, 2}, {2, 5}}
return: 2

풀이법

---

각 번호를 노드로 만들고, 각 노드가 이기는 노드를 win 리스트로, 지는 노드들을 lose 리스트로 저장.
각 노드들을 검사하여 A가 B한테 진다면, B가 이기는 노드들을 A가 이기는 노드 리스트에도 저장. 겹치지않게 HashSet으로 관리.
지는 노드들도 마찬가지로 해준다.
모든 노드들을 검사하는 반복문을 2번 돌려서 검사를 통과 했는데, 더 좋은 방법이 있을거 같은데 일단 생각이 안난다.

코드

---

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54

class Solution {     public int solution(int n, int[][] results) {         int answer = 0;         ArrayList<RankNode> list = new ArrayList<>();         list.add(new RankNode(0));         for(int i=1; i<=n; i++) {             list.add(new RankNode(i));         }         for(int[] r : results) {             list.get(r[1]).lose.add(r[0]);             list.get(r[0]).win.add(r[1]);         }         for(int k=0; k<2; k++) {              for(int i=1; i<=n; i++) {                  RankNode rn = list.get(i);                  HashSet<Integer> tmp = new HashSet<>();                  for(Integer win : rn.win) {                      for(Integer w: list.get(win).win) {                          tmp.add(w);                      }                  }                  rn.win.addAll(tmp);                  tmp = new HashSet<>();                  for(Integer lose: rn.lose) {                      for(Integer l: list.get(lose).lose) {                          tmp.add(l);                      }                  }                  rn.lose.addAll(tmp);              }         }         for(RankNode rn : list) {             int size = rn.win.size();             size += rn.lose.size();             if(size>=n-1) {                 answer++;             }         }         return answer;     } } class RankNode{     int key;     HashSet<Integer> lose;      HashSet<Integer> win;      boolean isRank;          public RankNode(int k) {         key = k;         lose= new HashSet<>();         win= new HashSet<>();         isRank = false;     } } Colored by Color Scripter

cs