[프로그래머스] 파이썬 문제풀이 - 순위

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

프로그래머스

처음에는 테이블을 작성해서 본인의 순위를 찾는것까지 구현했는데 순위를 아는 참가자 정보를 토대로 테이블을 업데이트 하는과정에서 복잡해져 다른 방법을 찾아봤다.

풀이

이 문제는 모든 노드로부터 모든 노드까지의 최단거리를 구할 수 있는 플로이드 와샬 알고리즘을 사용하면 쉽게 풀 수 있다. a선수가 b선수를 이겼다면 a선수는 b선수를 항상 이긴다는 사실에 집중해야한다. 문제에 적용해서 생각해보면 a선수와 b선수의 결과를 모르더라도 a와 c의 결과와 c와 b의 결과를 알면 a와b의 결과를 유추할 수 있는 것이다. 

    for k in range(n):
        for i in range(n):
            for j in range(n):
                if maps[i][j]==0:
                    if maps[i][k]==1 and maps[k][j]==1:
                        maps[i][j]=1
                    elif maps[i][k]==-1 and maps[k][j]==-1:
                        maps[i][j]=-1

기존 플로이드 와샬 알고리즘을 위와 같이 변형해서 풀 수 있는 것이다. 테이블을 모두 구하면 0의 개수를 체크해 확실하게 순위를 알 수 있는 참가자 수를 구할 수 있다.  

 

구현 코드

from collections import Counter

def solution(n, results):
    maps=[[0]*n for _ in range(n)]
    for a,b in results:
        maps[a-1][b-1]=1
        maps[b-1][a-1]=-1
    
    
    for k in range(n):
        for i in range(n):
            for j in range(n):
                if maps[i][j]==0:
                    if maps[i][k]==1 and maps[k][j]==1:
                        maps[i][j]=1
                    elif maps[i][k]==-1 and maps[k][j]==-1:
                        maps[i][j]=-1
    
    answer=0
    for i in range(n):
        if Counter(maps[i])[0]==1:
            answer+=1
    return answer

 

다른 답안

1. 가독성을 높이기 위해 리스트의 값을 숫자 대신 문자로 지정할 수도 있다.

def solution(n, results):
    total = [['?' for i in range(n)] for j in range(n)]

    for i in range(n):
        total[i][i] = 'SELF'

    for result in results:
        total[result[0]-1][result[1]-1] = 'WIN'
        total[result[1]-1][result[0]-1] = 'LOSE'

    for k in range(n):
        for i in range(n):
            for j in range(n):
                if total[i][k] == 'WIN' and total[k][j] == 'WIN':
                    total[i][j] = 'WIN'
                elif total[i][k] == 'LOSE' and total[k][j] == 'LOSE':
                    total[i][j] = 'LOSE'

    answer = 0

    for i in total:
        if '?' not in i:
            answer += 1

    return answer

 

배운 점

1. 알고리즘을 알아도 적용시키기 위해 떠올리는게 쉽지 않다. 반복적으로 생각해봐야겠다.