programmers - 순위

resilient

·

2021. 7. 21. 15:03

728x90
반응형

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

 

코딩테스트 연습 - 순위

5 [[4, 3], [4, 2], [3, 2], [1, 2], [2, 5]] 2

programmers.co.kr

  • 이 문제는 그래프 문제로 주어진 results 리스트를 활용해서 그래프를 먼저 그리고 시작했다.
  • 이긴 사람 집단과 진 사람 집단을 만들어서 먼저 그래프를 구현해줬다.
  • 이 문제의 포인트는 b가 a를 이겼을 때, c가 b를 이겼으면 c는 a보다 높은 순위라는 점이다.
  • 이 문제 예시에서도 2번이 5번을 이겼고, 2번이 1,3,4한테 졌으면 5번은 당연히 1,3,4보다는 아래 순위를 기록하게된다.
  • winner와 loser의 딕셔너리를 만들어주고, for문을 통해서 입력값 results를 통해 그래프를 만들어줬다.
  • 그리고 주어진 n만큼의 인원수를 for문을 돌리면서 누가 누구한테 졌고 이겼는지를 판단해서 위에 말했던 포인트를 유념해서 update해주는 방식으로 구현했다.
def solution(n, results):
    answer = 0
    winner = {i:set() for i in range(1,n+1)}
    loser = {i:set() for i in range(1,n+1)}
    for win, lose in results:
        winner[win].add(lose)
        loser[lose].add(win)
    for i in range(1,n+1):
        for lose in winner[i]:
            loser[lose].update(loser[i])
        for win in loser[i]:
            winner[win].update(winner[i])
    for i in range(1,n+1):
        if len(loser[i]) + len(winner[i]) == n-1:
            answer += 1
    return answer

 

반응형