[python] 프로그래머스 LV.03 - 순위

programmers.co.kr/learn/courses/30/lessons/49191

코딩테스트 연습 - 순위

[ 알고리즘 ]

단순구현

 

[문제 접근]

이 문제의 관건은 나 자신을 제외한 모든 사람과의 이기고,짐의 결과를 알고 있어야된다는 것이다.

이김 =1, 짐 =-1, 알 수 없음 =0으로 나타낸 리스트를 생성시켜주고

 

한 명의 정보에 대해서,

만약 a가 b,c,d 에게 지고 , e에겐 이겼다면,

 

1 ) e는 b,c,d에게 무조건 질 것이고,

2 ) b,c,d는 무조건 e를 이길 것이라는걸 알 수 있다.

 

이렇게 한명씩 모두 정보를 업데이트 시켜준 후,

각 행에서 0이 하나만 포함된 행을 count해주면 된다 ( 자기자신과의 결과는 모름으로)

 

[코드]

from collections import Counter
def solution(n, results):
    answer = 0
    
    graph=[[0]*n for _ in range(n)]
    
    for result in results:
        w= result[0]-1 # 이김
        l=result[1]-1 # 짐
        
        graph[w][l]=1 # 이김
        graph[l][w]=-1 # 짐
        
    for i in range(n):
        ptr=graph[i]
        win=[]
        lose=[]       
        for j in range(n):
            if ptr[j]==1: # i한테 진 애들
                lose.append(j)
            elif ptr[j]==-1: #i를 이긴 애들
                win.append(j)
        
        if len(lose)!=0 and len(win)!=0:
            for L in lose:
                for W in win:
                    graph[L][W]=-1
                    
            for W in win:
                for L in lose:
                    graph[W][L]=1
                    
    for List in graph:
        counter=Counter(List)
        
        if counter[0]==1:
            answer+=1
               
    return answer