[프로그래머스 lv 3] 순위

사용 언어 - Python3

문제 - 순위

https://school.programmers.co.kr/learn/courses/30/lessons/49191

프로그래머스

 

정답

해당 사람에게 이기고 진 사람 수 확인하기

플로이드-와샬 알고리즘 A->B, B->C ===> A->C

 

1. 이기고 진 관계 설정하기

dist_array = [[0]*n for _ in range(n)]

dist_array[이긴사람][진사람] = 1

 

2.i가 k를 이겼고, k가 j를 이겼다면, 자동으로 i는 j를 이겼다.

3번의 반복문을 통해 dist_array[i][j] = 1

 

dist_array

   0 1 2 3 4 (j)

0 0 1 0 0 1 => i는 j 에게 이겼다. 1번은 2,5번에게 이겼다. 

1 0 0 0 0 1 => 2번은 5번에게 이겼다.

2 0 1 0 0 1 => 3번은 2,5번에게 이겼다.

3 0 1 1 0 1 => 4번은 2,3,5번에게 이겼다.

4 0 0 0 0 0 => 5번은 아무에게도 이기지 않았다.

(i)

 

=> j는 i에게 졌다.

=> 1번은 모른다.

=> 2번은 1,3,4번에게 졌다.

=> 3번은 4번에게 졌다.

=> 4번은 모른다.

=> 5번은 1,2,3,4번에게 졌다.

 

3. 이기고 진 사람 횟수 확인하기

column_sum = [0]*n # 진 사람 수

row_sum = [0]*n # 이긴 사람수

 

4. 자기를 제외한 모든 사람에게 이기고 졌다면, 순위 판단이 가능하다

column_sum[index] + row_sum[index] == n-1

answer += 1 # 순위판단이 가능한 사람 수

return answer

 

def solution(n, results):    
    dist_array = [[0]*n for _ in range(n)]
    
    # i가 j를 이겼다
    for result_win, result_lose in results:
        dist_array[result_win-1][result_lose-1] = 1

    for k in range(n):
        for i in range(n):
            for j in range(n): 
                # i와 j가 대결하지 않았을때
                # i가 k라는 사람한테도 이기고 k가 j라는 사람한테도 이겼다면, i는 j에게 이겼다. 
                # i > k, k > j => i > j
                if dist_array[i][j] == 0 and dist_array[i][k] and dist_array[k][j]:
                    dist_array[i][j] = 1
    
    # 행/열 = 이기고/진사람 수
    column_sum = [0]*n
    row_sum = [0]*n
    
    for row in range(n):
        for column in range(n):
            column_sum[column] += dist_array[row][column]
            row_sum[row] += dist_array[row][column]
    
    # index 선수의 순위 판단이 가능한가?
    answer = 0 
    for index in range(n):
        # n-1명한테 이기고 졌다면, 순위는 확실하다 
        if column_sum[index] + row_sum[index] == n-1:
            answer+=1

    return answer

 

 

레퍼런스

https://life318.tistory.com/4

[프로그래머스] 순위(Floyd-Warshall Algorithm)