[python] 이코테 - 정확한 순위

출처 : 이것이 취업을 위한 코딩테스트다 with Python, 정확한 순위

이것이 취업을 위한 코딩 테스트다 with 파이썬

 

 

먼저, 생각해야 할 부분

 

1. n명 중 정확한 순위를 알 수 있다는 것은 내 아래로 A명과 내 위로 B명을 더했을 때 n-1 명이라는 것과 같다.

2. 내 점수보다 아래 혹은 위임을 알 수 있는 방법은 해당 노드를 방문할 수 있는지 여부를 통해 알 수 있다.

3. r = 점수가 낮은 학생, c = 점수가 높은 학생으로 정했을 때, 

     1번 행은 1보다 1번 학생보다 점수가 높은 학생들의 방문 가능 여부를 보여준다.

     반대로 1번 열은 1번 학생보다 점수가 낮은 학생들의 방문 가능 여부를 보여준다.

---

 

풀이

 

INF = float('inf')

def solution(n, count, comp_student):
    # low high
    # 성적 순위를 정확히 알 수 있는 학생
        # 나보다 낮은 학생 + 나보다 높은 학생 = 전체 - 1이면 알 수 있는 거
        
    answer = 0

    matrix = [[INF for _ in range(n)] for _ in range(n)]

    for low, high in comp_student:
        matrix[low - 1][high - 1] = 1

    for k in range(n):
        for i in range(n):
            for j in range(n):
                matrix[i][j] = min(matrix[i][j], matrix[i][k] + matrix[k][j])

    row_sum = [sum([1 if num != INF else 0 for num in row]) for row in matrix]
    col_sum = [sum([1 if num != INF else 0 for num in col]) for col in zip(*matrix)]

    for r, c in zip(row_sum, col_sum):
        if r + c == n - 1:
            answer += 1

    return answer

n, count = map(int, input().split())

comp_student = [list(map(int, input().split())) for _ in range(count)]

print(solution(n, count, comp_student))

 

---

알게 된 점

 

플로이드 워셜의 가능성

 

플로이드 워셜은 모든 노드를 시작으로 다른 모든 노드에 대한 최단 거리를 보여준다.

이를 거리를 제외하고 본다면, 단순 방문 가능 여부로 사용이 가능하다.

 

Reference

이것이 취업을 위한 코딩테스트다 with Python