[Python/코테] 프로그래머스 순위

순위

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

프로그래머스

알고리즘 설계

💡idea.

모든 선수와의 경기 결과가 있어야, 정확한 순위 분석이 가능하다. 예를 들어, 예시에서 나온 4번 선수는 1, 5번 선수와의 경기 결과가 없어서 1위라고 판단할 수 없다. 즉 주어진 배열에서 각 선수마다 (1) 경기 횟수 (2) 이긴 횟수를 알아야 한다. 그러나 배열에 나오지 않은 경기 결과로도 순위를 간접적으로 파악할 수 있다. 예를 들어, 선수 A가 선수 B를 이기고, 선수 B가 선수 C를 이겼다면, 선수 A가 선수 C보다 강하다는 추가 정보를 미루어 짐작할 수 있는 것이다. 

 

A → B, B  →  C 이면, A  →  C라는 의미이므로 플로이드-와샬 알고리즘을 활용할 수 있다.

최단 경로를 구하는 것은 아니지만, "거쳐가는 노드"를 활용한다는 점에 집중하면 될 것 같다.

2024.06.15 - [Algorithm] - [Python/코테] 플로이드 와샬 알고리즘 - 개념, 코드

[Python/코테] 플로이드 와샬 알고리즘 - 개념, 코드

 

🎲step.

1. 결과를 저장하는 이차원 배열을 생성한다. [i][j]에 대해 i선수가 j선수를 이겼으면 1, 졌으면 -1을 값으로 저장한다.

2. 주어진 results 배열을 사용하여 결과를 이차원 배열에 저장한다.

3. 플로이드-와샬 알고리즘을 적용하여, results에는 명시되지 않은 승패 정보까지 저장한다.

4. n명의 선수와의 승패 결과가 저장되어있어 순위를 매길 수 있는 선수의 수를 계산한다. 

 

알고리즘 구현

def solution(n, results):
    # 무한대 값 설정
    INF = float('inf')
    
    # 1. 결과를 저장하는 이차원 배열을 생성한다. 
    graph = [[INF] * n for _ in range(n)]
    
    # 2. 주어진 results 배열을 사용하여 결과를 이차원 배열에 저장한다.
    # 자기 자신과의 경기는 0으로 저장한다.
    for i in range(n):
        graph[i][i] = 0

    # [i][j]에 대해 i선수가 j선수를 이겼으면 1, 졌으면 -1을 값으로 저장한다.
    for winner, loser in results:
        graph[winner-1][loser-1] = 1
        graph[loser-1][winner-1] = -1
   
   
   # 3. 플로이드-와샬 알고리즘을 적용하여, 
   # results에는 명시되지 않은 승패 정보까지 저장한다.
    for k in range(n):
        for i in range(n):
            for j in range(n):
                if graph[i][j] == INF:
                    if graph[i][k] == 1 and graph[k][j] == 1:
                        graph[i][j] = 1
                    elif graph[i][k] == -1 and graph[k][j] == -1:
                        graph[i][j] = -1
    
    
    answer = 0
    for i in range(n):
        count = 0
        for j in range(n):
            if graph[i][j] != INF:
                count += 1
        # 4. n명의 선수와의 승패 결과가 저장되어있어 
        # 순위를 매길 수 있는 선수의 수를 계산한다. 
        if count == n:
            answer += 1

    return answer

나다어

나는 다음에 어떻게 풀까

 

• 배열의 인덱스를 적극 활용하자. 배열에서 활용할 수 있는 값이 인덱스와 값 2가지인 셈이다.
  이번 문제에서는 .list[a][b] 에 대해 'a가 b를 이겼는지'로 활용했다.
• 문제를 그래프로 표현할 수 있는지 확인하고, 가능하면 그래프 알고리즘을 활용하자.
• 플로이드-와샬 알고리즘을 잘 기억하자