import java.util.*;
class Solution {
private boolean changed;
public int solution(int n, int[][] results) {
int[][] resultBoard = new int[n][n];
for(int i=0; i< results.length; i++){
results[i][0]--;
results[i][1]--;
int idxWinner = results[i][0];
int idxloser = results[i][1];
resultBoard[idxWinner][idxloser] = 1;
resultBoard[idxloser][idxWinner] = -1;
}
changed = true;
while(changed){
changed = false;
for(int i=0; i< n; i++){
for(int j=0; j<n; j++){
if(resultBoard[i][j] == 1) resultBoard[i] = mergeResultWin( resultBoard[i], resultBoard[j]);
else if(resultBoard[i][j] == -1) resultBoard[i] = mergeResultLose( resultBoard[i], resultBoard[j]);
}
}
}
//선수 수 확인
return checkReturnN(resultBoard, n);
}
//최종 확인
private int checkReturnN(int[][] result,int n){
int count = 0;
for(int i=0; i<result.length ; i++){
int rCount = n-1;
for(int j=0; j<result[0].length; j++){
if(result[i][j] != 0) rCount--;
}
if(rCount == 0) count++;
}
return count;
}
private int[] mergeResultWin(int[] a, int[] target){
for(int i=0; i<a.length; i++){
if(target[i] == 1 && a[i] != 1) {
a[i] = 1;
changed = true;
}
}
return a;
}
private int[] mergeResultLose(int[] a, int[] target){
for(int i=0; i<a.length; i++){
if(target[i] == -1 && a[i] != -1) {
a[i] = -1;
changed = true;
}
}
return a;
}
}
1) graph 배열 생성
2) 승패 여부에 따라 merge 작업 진행
3) 최종적으로 결과가 n개있을때, 결과에 포함
정확성 테스트
정확성 테스트
테스트 1 〉 통과 (0.04ms, 52.7MB)
테스트 2 〉 통과 (0.07ms, 52.9MB)
테스트 3 〉 통과 (0.11ms, 55.5MB)
테스트 4 〉 통과 (0.12ms, 52.2MB)
테스트 5 〉 통과 (1.98ms, 52.6MB)
테스트 6 〉 통과 (1.56ms, 52.9MB)
테스트 7 〉 통과 (11.77ms, 53.9MB)
테스트 8 〉 통과 (25.04ms, 53MB)
테스트 9 〉 통과 (40.06ms, 57.2MB)
테스트 10 〉 통과 (22.51ms, 55.8MB)
def mergeResultWin(a, target, check):
for i in range(0, len(a), 1):
if target[i] == 1 and a[i] != 1:
a[i] = 1
check = True
return check
def mergeResultLose(a, target, check):
for i in range(0, len(a), 1):
if target[i] == -1 and a[i] != -1:
a[i] = -1
check = True
return check
def checkReturnN(graph, n):
count = 0
for i in range(0, len(graph), 1):
rCount = n - 1
for j in range(0, len(graph[0]), 1):
if graph[i][j] != 0:
rCount -= 1
if rCount == 0:
count += 1
return count
def solution(n, results):
answer = 0
graph = [[0 for i in range(n)] for i in range(n)]
for start, end in results:
graph[start - 1][end - 1] = 1
graph[end - 1][start - 1] = -1
check = True
while check:
check = False
for start in range(0, n):
for end in range(0, n):
if graph[start][end] == 1:
check = mergeResultWin(graph[start], graph[end], check)
elif graph[start][end] == -1:
check = mergeResultLose(graph[start], graph[end], check)
return checkReturnN(graph, n)
정확성 테스트
정확성 테스트
테스트 1 〉 통과 (0.06ms, 10.3MB)
테스트 2 〉 통과 (0.10ms, 10.3MB)
테스트 3 〉 통과 (0.28ms, 10.3MB)
테스트 4 〉 통과 (0.34ms, 10.2MB)
테스트 5 〉 통과 (3.62ms, 10.3MB)
테스트 6 〉 통과 (7.04ms, 10.4MB)
테스트 7 〉 통과 (52.14ms, 10.3MB)
테스트 8 〉 통과 (108.27ms, 10.5MB)
테스트 9 〉 통과 (142.45ms, 10.6MB)
테스트 10 〉 통과 (109.18ms, 10.3MB)
def solution(n, results):
answer = 0
win, lose = defaultdict(set), defaultdict(set)
for result in results:
lose[result[1]].add(result[0])
win[result[0]].add(result[1])
for i in range(1, n + 1):
for winner in lose[i]: win[winner].update(win[i])
for loser in win[i]: lose[loser].update(lose[i])
for i in range(1, n+1):
if len(win[i]) + len(lose[i]) == n - 1: answer += 1
return answer
1) 승자 배열과 패자 배열 생성
2) 승패 순환하며 서로 value merge작업 진행
3) 최종적으로 결과가 n개있을때, 결과에 포함
정확성 테스트
정확성 테스트
테스트 1 〉 통과 (0.02ms, 10.2MB)
테스트 2 〉 통과 (0.02ms, 10.2MB)
테스트 3 〉 통과 (0.05ms, 10.2MB)
테스트 4 〉 통과 (0.04ms, 10.2MB)
테스트 5 〉 통과 (0.44ms, 10.2MB)
테스트 6 〉 통과 (0.83ms, 10.4MB)
테스트 7 〉 통과 (2.26ms, 10.4MB)
테스트 8 〉 통과 (3.64ms, 11MB)
테스트 9 〉 통과 (5.36ms, 11.2MB)
테스트 10 〉 통과 (5.07ms, 11.3MB)
최소한의 반복으로 인해 성능 증가.!