[ 프로그래머스 / LV3 / 자바 JAVA ] 순위

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

프로그래머스

---

한 번 해결한 문제를 자바로 바꿔서 풀고 작성한 글입니다.
문제의 자세한 풀이법은 아래의 링크를 참고해주세요
https://blogeon.tistory.com/entry/%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%A8%B8%EC%8A%A4-LV3-%ED%8C%8C%EC%9D%B4%EC%8D%AC-Python-%EC%88%9C%EC%9C%84

 

코드 - Set자료형 활용

---

import java.util.*;

class Solution {
    public int solution(int n, int[][] results) {
        int answer = 0;
        HashMap<Integer,Set<Integer>> winning = new HashMap<>();
        HashMap<Integer,Set<Integer>> losing = new HashMap<>();
        for (int i = 1; i <= n; i++) {
            winning.put(i,new HashSet<Integer>());
            losing.put(i,new HashSet<Integer>());
        }
        
        for (int[] r : results){
            winning.get(r[0]).add(r[1]); // 나에게 진 사람
            losing.get(r[1]).add(r[0]); // 나에게 이긴 사람
        }
        for (int i = 1; i <= n; i++){
            for (int winner_to_me: losing.get(i)) winning.get(winner_to_me).addAll(winning.get(i));
            for (int loser_to_me: winning.get(i)) losing.get(loser_to_me).addAll(losing.get(i));
        } 
        
        for (int i=1; i <= n; i++){
            if (winning.get(i).size() + losing.get(i).size() == n-1) answer ++;
        }
        
        return answer;
    }
}

 

풀이 - Set자료형 활용

---

 

문제풀이의 핵심은 "순위를 알 수 있다" 라는 말은 "나보다 실력이 좋은 사람 + 나보다 실력이 좋지 않은 사람 == n-1" 이라는 것이다.

 

따라서 나보다 실력이 좋은 사람과 나보다 실력이 좋지 않은 사람을 알아야 하는데 다음과 같은 상황이 발생할 수 있다.

• a가 b를 이긴다.
• b가 c를 이긴다.
• 따라서 a는 c를 이긴다.

(a,b)와 (b,c)는 주어지는데 (a,c)는 주어지지 않아도 a는 c를 이긴다는 것을 계산하고 누적시키는 것이 이 문제풀이의 핵심과정이라고 할 수 있다.

 

이 풀이에서는 Set자료형을 사용해서 나를 이기는 사람과 나에게 지는 사람을 모두 저장했다.

파이썬에서는 update로 가능했던 set 합치기 연산이 자바에서는 addAll로 가능했다.

또한 자바에서 set의 길이는 length가 아닌 size()메서드를 사용해야 한다.

---

코드 - 플로이드 워샬

---

class Solution {
    public int solution (int n, int[][] results){
        boolean[][] game =  new boolean[n][n];
        int answer = 0;
        for(int i=0; i<results.length; i++){ game[results[i][0]-1][results[i][1]-1]=true; }

        for(int i=0; i<n; i++){
            for(int j=0; j<n; j++){
                for(int k=0; k<n; k++){
                    if(game[j][i]&&game[i][k]){game[j][k]=true;}
                }
            }
        }

        for(int i=0; i<n; i++){
            int result=0;
            for(int j=0; j<n; j++){
                if(game[i][j] || game[j][i]){result++;}
            }
            if(result==n-1){answer++;}
        }
        return answer;
    }
}

 

풀이 - 플로이드 워샬

---

이 풀이도 결국 핵심은 위의 Set자료형을 활용한 코드와 동일한데 boolean자료형을 사용했다.

사실 이 문제에서 플로이드 워샬을 생각해보지 못했는데 지금 생각해보니 이런 체인이 이루어진 관계를 정리할 때에는 플로이드 워샬이 맞는 것 같다.

 

for(int j=0; j<n; j++){
    if(game[i][j] || game[j][i]){result++;}
}

이 코드가 아주 간단하게 핵심을 잘 작성한 것 같다.

game[i][j] == 내가 이긴 사람

game[j][i] == 나에게 이긴 사람

두 값 중 하나라도 true라면 나와 승부관계가 있는 사람이므로 덧셈해준다.