알고리즘/프로그래머스
[프로그래머스] 순위 -Java
dkwjdi
2020. 12. 25. 15:05
https://programmers.co.kr/learn/courses/30/lessons/49191
코딩테스트 연습 - 순위
5 [[4, 3], [4, 2], [3, 2], [1, 2], [2, 5]] 2
programmers.co.kr
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;
graph[results[i][1]][results[i][0]] = -1;
}
for (int k = 1; k <= n; k++) { // 들렀다 가는곳
for (int i = 1; i <= n; i++) { // 시작
for (int j = 1; j <= n; j++) { // 도착
if (i == j || graph[i][j] != 0) continue;
if (graph[i][k] == graph[k][j]) graph[i][j] = graph[i][k];
}
}
}
loop: for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
if (i == j) continue;
if (graph[i][j] == 0) continue loop;
}
answer++;
}
return answer;
}
}
소요시간 : 20분
우선 플로이드 와샬 알고리즘을 사용하였습니다.
N이 100밖에 안되기 때문에 N^3을 사용하더라도 충분하다는 생각으로 하였습니다.
2차원 배열에 이긴경기는 1, 진 경기는 -1로 표시하였습니다.
k = 경유지
i = 시작지
j = 도착지
로 놓고 풀었습니다!
예전에 풀어봤던 문제인데 플로이드 와샬이 가물가물한거 같아서 다시 풀어봤습니다!