프로그래머스 - 순위(파이썬, LV3)

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

코딩테스트 연습 - 순위

정답

출처 : 멍토의 IT블로그

와샬플로이드 알고리즘으로 접근하는 방식

그러나, 그렇게까지 생각이 안나서, 로직만을 생각했다. 로직은 맞았으나 구현방식이 계속 틀려서 정답을 참조했다ㅠㅠ

 

win[i] ->  {} i가 이긴 사람들 집합

lose[i] -> {} i를 이긴 사람들 집합

의 리스트를 준비하고 경기결과를 전체 파싱해서 채워 넣는다.

 

그리고 이제 i를 이긴 사람들에게 이긴 사람들은 전부 i를 이길 수 있다

또한 i에게 진사람들은 i가 진사람들에게도 전부 진다.

 

이 두 명제가 구현하기에 굉장히 어렵고 조금 난해하다. 

def solution(n, results):
    win = {x:set() for x in range(1, n+1)}
    lose = {x:set() for x in range(1, n+1)}
    for winner, loser in results:
        win[winner].add(loser)
        lose[loser].add(winner)
        
    for i in range(1, n+1):
        # i가 진 사람들(승자들)은 i가 이긴 사람들도 이긴다
        for winner in lose[i]:
            win[winner].update(win[i])
        # i에게 진 사람들(패자들)은 i가 진사람들에게도 진다
        for loser in win[i]:
            lose[loser].update(lose[i])
    
    answer = 0
    for i in range(1, n+1):
        if len(win[i]) + len(lose[i]) == n-1:
            answer += 1
    return answer

 

 

틀린 접근 1)

풀이를 접근할 때, 처음에는 

list 에 Set을 통해 애매한 순위를 계속 유지해나가다가 Set의 순위가 명확해지면 결과를 도출하려고 했다.

 

> 그러나 애초에 Set의 순위를 언제까지 유지할 수 있을지 불분명하기에 해당 로직은 틀림

 

틀린 접근 2)

큰 명제2. 나를 이긴 사람에게 이긴사람들 추가, 나에게 진사람에게 진사람 추가

해당 명제를 구현하는 방식이 잘못됨

def solution(n, results):
    answer = 0
    
    # 내가 이긴 대상
    winMem = [set() for _ in range(n+1)]
    
    # 내가 진 대상
    loseMem = [set() for _ in range(n+1)]
    
    for i in range(n):
        # 내가 이긴 사람 추가
        winMem[results[i][0]].add(results[i][1])
        # 내가 진 사람 추가
        loseMem[results[i][1]].add(results[i][0])
    
    for i in range(1,n+1):
        # 내가 이긴 사람에게 진 사람들에 대해서 
        # 패배 목록 추가
        for winOfLose in winMem[i]:
            loseMem[winOfLose] = loseMem[winOfLose] | loseMem[i] 

        # 나를 이긴 사람에게 이긴 사람들에 대해서
        # 승리 목록 추가
        for winOfWin in loseMem[i]:
            winMem[winOfWin] = winMem[winOfWin] | winMem[i] 
            
    # 전체 카운트
    for i in range(1,n+1):
        if len(winMem[i]) + len(loseMem[i]) == n-1:
            answer+=1
            
    return answer