알고리즘 문제/Programmers
[프로그래머스] 순위 - Java
Praetoriani
2021. 6. 4. 01:00
- 문제 링크
- 참고 : 플로이드-워셜 알고리즘
풀이 과정
Floyd-Warshall 알고리즘을 되짚어보고 진행하면 수월하다.
문제에 주어지는 조건 (선수의 수 및 전적)을 int 형 2차원 배열로 표현할 수 있다. 주어진 예제라면 아래 표와 같이 표현된다.
- int 타입 2차원 배열로 표현하였으므로 위 표의 빈칸도 0으로 초기화되어있다.
- 따라서, 0은 자기 자신 또는 결과 모름을 의미한다.
- 1은 상대에게 승리했음을, -1은 상대에게 패배했음을 의미한다.
- int 타입 2차원 배열로 표현하였으므로 위 표의 빈칸도 0으로 초기화되어있다.
이후 1번 선수부터 아래의 과정을 반복한다.
i
번 선수가 승리한 상대 선수를 찾는다. 주어진 예제에서는 1번 선수가 2번 선수를 상대로 승리했다.- 1번의 결과로 찾은 선수가 승리한 상대 선수를 찾는다. 주어진 예제에서는 2번 선수가 5번 선수를 상대로 승리했다.
- 1번의 결과로 찾은 선수가 2번의 결과로 찾은 선수를 상대로 이겼다고 기록한다.
위 과정을 모든 선수에 대해서 반복하면 최종 대진 결과가 적힌 표를 얻을 수 있다. 문제의 예제라면 아래의 표와 같이 갱신된다.
최종 결과가 적힌 표를 가지고 다시 전체 선수에 대해 순회하며 0이 아닌 결과의 수를 센다. 이 결과가
n - 1
이라면 순위를 알 수 있다.
Code
import java.util.Arrays;
class Solution {
public int solution(int n, int[][] results) {
int[][] matchResults = new int[n][n];
// setup
for (int[] result : results) {
int winner = result[0] - 1;
int loser = result[1] - 1;
matchResults[winner][loser] = 1; // win
matchResults[loser][winner] = -1; // lose
}
// a → b 이고 b → c 이면 a → c
for (int b = 0; b < n; b++) {
for (int a = 0; a < n; a++) {
if (matchResults[a][b] <= 0) { // a가 b에게 이긴 경우에만 진입
continue;
}
for (int c = 0; c < n; c++) {
if (matchResults[b][c] > 0 && matchResults[a][c] == 0) {
// a가 c를 이겼는지는 아직 모를 때, b가 c에게 이겼으면
matchResults[a][c] = 1; // a도 c에게 승리
matchResults[c][a] = -1;
}
}
}
}
int answer = 0;
for (int[] matchResult : matchResults) {
answer += (int) Arrays.stream(matchResult).filter(result -> result != 0).count() == (n - 1) ? 1 : 0;
}
return answer;
}
}
결과
