코테/프로그래머스

[프로그래머스/Lv. 2] 순위 (JAVA)

imname1am 2023. 10. 5. 02:19
반응형

🔺 문제

 

프로그래머스

코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.

programmers.co.kr

 

 

🔺 코드

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
import java.util.*;
 
class Solution {
    public int solution(int n, int[][] results) {
        int answer = 0;
        int[][] graph = new int[n + 1][n + 1];  // 인접 행렬
        
        // 이기는 경우의 수 입력
        for(int i = 0 ; i < results.length ; i++)   graph[results[i][0]][results[i][1]] = 1;    
        
        // 플로이드-워셜
        for(int k = 0 ; k <= n ; k++) {
            for(int i = 0 ; i <= n ; i++) {
                for(int j = 0 ; j <= n ; j++) {
                    if(graph[i][k] == 1 && graph[k][j] == 1) {  // 간접적으로 이길 경우의 수 : i → k, k → j라면, i → j
                       graph[i][j] = 1;
                    }
                }
            }
        }
        
        for(int i = 1 ; i <= n ; i++) {
            int cnt = 0;    // 지고 이긴 경우의 수 (= 0이 아닌 값)
            
            for(int j = 1 ; j <= n ; j++) {
                if(graph[i][j] == 1 || graph[j][i] == 1) { // 두 선수 간 승부 결과 파악이 가능한 경우
                    cnt++;
                }
            }
            
            if(cnt == n - 1)    // 선수 순위 확정 가능한 경우
                answer++;
        }
        
        return answer;
    }
}
cs

 

 

🧩 해결 아이디어

• 플로이드-워셜 ; 모든 정점에서 다른 모든 정점으로의 최단 거리 계산.

- 여기서 최단 거리까지는 계산할 필요 없고, 도달 가능한지만 확인하면 됨

 

 


🔺 다른 풀이들

- 두 선수 A B 간 승부 결과를 1과 -1로 표현하셨다. (1 : A가 이김 / -1 : B가 이김)

그림 과정 설명도 복습할 때 봐야겠다.

 

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

문제 https://programmers.co.kr/learn/courses/30/lessons/49191# 코딩테스트 연습 - 순위 5 [[4, 3], [4, 2], [3, 2], [1, 2], [2, 5]] 2 programmers.co.kr n명의 권투선수가 권투 대회에 참여했고 각각 1번부터 n번까지 번호를 받

gom20.tistory.com

 


💬 느낀 점

플로이드 워셜은 DP 기법을 활용한 알고리즘...

그래프 문제라고 해서 DFS랑 BFS 쓸 생각만 했었는데...

분발하자!

 

 

1회독 2회독 3회독 4회독 5회독
V        

(참고)

 

[프로그래머스] 순위-JAVA

문제 링크 https://programmers.co.kr/learn/courses/30/lessons/49191 코딩테스트 연습 - 순위 5 [[4, 3], [4, 2], [3, 2], [1, 2], [2, 5]] 2 programmers.co.kr 풀이 과정 필자는 이 문제를 보고 순서대로 로직을 정리해봤다. 1.

born2bedeveloper.tistory.com

 

 

[프로그래머스] 순위 - Java

코딩테스트 연습 - 순위 5 [[4, 3], [4, 2], [3, 2], [1, 2], [2, 5]] 2 programmers.co.kr 문제 설명 n명의 권투선수가 권투 대회에 참여했고 각각 1번부터 n번까지 번호를 받았습니다. 권투 경기는 1대1 방식으로

bellog.tistory.com

 

반응형