[문제 이름 : 순위 (프로그래머스, Lv 3) ]
문제 url : https://school.programmers.co.kr/learn/courses/30/lessons/49191
내가 작성한 코드는 아래와 같다.
import java.util.*;
class Solution {
public int solution(int n, int[][] results) {
// 승리, 패배 정보를 저장할 리스트 배열
ArrayList<Integer>[] wins = new ArrayList[n + 1];
ArrayList<Integer>[] loses = new ArrayList[n + 1];
for (int i = 1; i <= n; i++) {
wins[i] = new ArrayList<>();
loses[i] = new ArrayList<>();
}
// 승리, 패배 정보 저장
for (int[] result : results) {
int winner = result[0];
int loser = result[1];
wins[winner].add(loser); // winner가 이긴 사람들
loses[loser].add(winner); // loser가 진 사람들
}
int answer = 0;
// 각 선수에 대해 정확한 순위를 매길 수 있는지 판단
for (int i = 1; i <= n; i++) {
boolean[] visitedWins = new boolean[n + 1];
boolean[] visitedLoses = new boolean[n + 1];
// i 선수가 이긴 사람들 탐색
int winCount = bfs(wins, visitedWins, i);
// i 선수가 진 사람들 탐색
int loseCount = bfs(loses, visitedLoses, i);
// 정확한 순위를 매길 수 있는 경우 (총합이 n-1인 경우)
if (winCount + loseCount == n - 1) {
answer++;
}
}
return answer;
}
// BFS를 사용하여 탐색
private int bfs(ArrayList<Integer>[] list, boolean[] visited, int start) {
Queue<Integer> queue = new LinkedList<>();
queue.add(start);
visited[start] = true;
int count = 0;
while (!queue.isEmpty()) {
int current = queue.poll();
for (int next : list[current]) {
if (!visited[next]) {
visited[next] = true;
queue.add(next);
count++;
}
}
}
return count;
}
}
[풀이 과정]
1. 인접리스트 형태로 승리/패배 정보를 저장한다. -> results 배열을 순회하며, 각 경기의 승리자, 패배자를 추가한다.
2. bfs 탐색을 통해, 이긴 사람들과 진 사람들을 각각 탐색한다. winCount는 해당 선수가 이긴 사람들의 수를, lossCount는 해당 선수가 진 사람들의 수를 의미한다.
3. winCount + loseCount가 n-1과 같다면, 이는 정확한 순위를 매길 수 있음을 의미하므로, 결과값에 ++ 해준다.
n-1인 이유는, 자기 자신을 제외한 모든 상대와의 승패 관계가 명확해야 순위를 결정할 수 있기 때문이다.
다른 사람들이 푼 방법을 보니, 플로이드-워셜 알고리즘으로 풀이한 방법이 있었다.
class Solution {
public int solution(int n, int[][] results) {
int[][] dist = new int[n + 1][n + 1];
int INF = 1000000; // 충분히 큰 값으로 초기화
// 초기화
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
if (i == j) {
dist[i][j] = 0;
} else {
dist[i][j] = INF;
}
}
}
// 승리 정보 반영
for (int[] result : results) {
int winner = result[0];
int loser = result[1];
dist[winner][loser] = 1;
}
// 플로이드-워셜 알고리즘 수행
for (int k = 1; k <= n; k++) {
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
if (dist[i][j] > dist[i][k] + dist[k][j]) {
dist[i][j] = dist[i][k] + dist[k][j];
}
}
}
}
// 정확히 순위를 매길 수 있는 선수 찾기
int answer = 0;
for (int i = 1; i <= n; i++) {
boolean canDetermineRank = true;
for (int j = 1; j <= n; j++) {
if (i != j && dist[i][j] == INF && dist[j][i] == INF) {
canDetermineRank = false;
break;
}
}
if (canDetermineRank) {
answer++;
}
}
return answer;
}
}
1. 자기 자신과의 거리는 0으로, 초기화에는 dist 배열은 INF로 초기화한다.
2. results 배열 정보를 dist 배열에 반영하여 초기화한다.
3. 플로이드-워셜 알고리즘을 수행하여, 각 중간 노드 k를 경유하는 모든 경로를 업데이트하여 최단 경로를 계산한다.
4. 모든 선수 i에 대하여, 다른 선수 j에 대해 i->j 또는 j->i로 이동할 수 있는지 확인하여, 정확한 순위를 매길 수 있는 선수를 찾는다.
-> 이는 O(N^3)의 시간 복잡도를 가진다.
풀이 시간 : 30분
내일은 Deque 알고리즘에 대하여 복습하고, 관련된 문제들을 풀이해보려 한다.