프로그래머스 순위 (코딩테스트 고득점 Kit, 그래프)

문제 설명

n명의 권투선수가 권투 대회에 참여했고 각각 1번부터 n번까지 번호를 받았습니다. 권투 경기는 1대1 방식으로 진행이 되고, 만약 A 선수가 B 선수보다 실력이 좋다면 A 선수는 B 선수를 항상 이깁니다. 심판은 주어진 경기 결과를 가지고 선수들의 순위를 매기려 합니다. 하지만 몇몇 경기 결과를 분실하여 정확하게 순위를 매길 수 없습니다.

선수의 수 n, 경기 결과를 담은 2차원 배열 results가 매개변수로 주어질 때 정확하게 순위를 매길 수 있는 선수의 수를 return 하도록 solution 함수를 작성해주세요.

제한 사항

• 선수의 수는 1명 이상 100명 이하입니다.
• 경기 결과는 1개 이상 4,500개 이하입니다.
• results 배열 각 행 [A, B]는 A 선수가 B 선수를 이겼다는 의미입니다.
• 모든 경기 결과에는 모순이 없습니다.

입출력 예

n	results	return
5	[[4, 3], [4, 2], [3, 2], [1, 2], [2, 5]]	2

입출력 예 설명

2번 선수는 [1, 3, 4] 선수에게 패배했고 5번 선수에게 승리했기 때문에 4위입니다.

5번 선수는 4위인 2번 선수에게 패배했기 때문에 5위입니다.

풀이

• 멍청이 같은 무지성 코딩으로 인해 주말이 모두 사라졌다.
  • 처음에 행렬로 그래프 만들어서 win/lose를 하나의 그래프로 해보려고 했는데
  • 탐색하는데 왜 무한루프가 되지...? ㅋㅋㅋ
  • 뭔지 모르겠지만 테케 4번만 풀리고 도저히 안되서
• 그 다음엔 그냥 배열에 순서대로 넣으면서 정렬해서 순서 맞춰보려고 했다.
  • 8,[3,4,5], 1, [2,6,7]
  • 이런 식으로 나오면 8과 1만 순위를 알 수 있고, 나머지는 모르는 걸로
  • 근데 이것도 하나보니 무한루프가 되어 버리는 것 같고...
• 결국 하나 하나 뜯어서 그리면서 한줄 한줄 ㅡ.ㅡ;;;

def solution(n, results):
    answer = 0
    wingraph = [[0 for _ in range(n+1)] for _ in range(n+1)]
    losegraph = [[0 for _ in range(n+1)] for _ in range(n+1)]
    sumgraph = [[0 for _ in range(n+1)] for _ in range(n+1)]
    
    for win,lose in results:
        wingraph[win][lose] += 1
        losegraph[lose][win] += 1
    
    for i in range(1,n+1):
        for j in range(1,n+1):
            
            if wingraph[i][j] == 1:
                for k in range(1,n+1):
                    if wingraph[k][i] == 1:
                        wingraph[k][j] = 1
                        
            if losegraph[i][j] == 1:
                for k in range(1,n+1):
                    if losegraph[k][i] == 1:
                        losegraph[k][j] = 1

    # print("wingraph")
    # for i in wingraph: print(i)
    # print("wingraph")
    # for i in losegraph: print(i)
    
    for i in range(1,n+1):
        for j in range(1,n+1):
            sumgraph[i][j] = wingraph[i][j] + losegraph[i][j]
        if sum(sumgraph[i]) == n-1:
            answer += 1
                
    #print("sumgraph")
    #for i in sumgraph: print(i)
    
    return answer
    
정확성  테스트
테스트 1 〉	통과 (0.05ms, 10.3MB)
테스트 2 〉	통과 (0.08ms, 10.2MB)
테스트 3 〉	통과 (0.21ms, 10.2MB)
테스트 4 〉	통과 (0.19ms, 10.2MB)
테스트 5 〉	통과 (2.08ms, 10.2MB)
테스트 6 〉	통과 (4.38ms, 10.2MB)
테스트 7 〉	통과 (22.46ms, 10.4MB)
테스트 8 〉	통과 (57.77ms, 10.6MB)
테스트 9 〉	통과 (68.58ms, 10.5MB)
테스트 10 〉	통과 (110.54ms, 10.7MB)

• 점점 난이도가 올라가면서 제대로 못 푸는 것 같다.
• 고수의 풀이를 보도록 하자.
  • 와 쩐다. 이게 뭐지??
    • 아 이렇게 하는거구나... ㅡ.ㅡ

from collections import defaultdict
def solution(n, results):
    answer = 0
    win, lose = defaultdict(set), defaultdict(set)
    for result in results:
            lose[result[1]].add(result[0])
            win[result[0]].add(result[1])

    for i in range(1, n + 1):
        for winner in lose[i]: win[winner].update(win[i])
        for loser in win[i]: lose[loser].update(lose[i])

    for i in range(1, n+1):
        if len(win[i]) + len(lose[i]) == n - 1: answer += 1
    return answer
    
정확성  테스트
테스트 1 〉	통과 (0.01ms, 10.3MB)
테스트 2 〉	통과 (0.02ms, 10.2MB)
테스트 3 〉	통과 (0.05ms, 10.2MB)
테스트 4 〉	통과 (0.03ms, 10.2MB)
테스트 5 〉	통과 (0.29ms, 10.3MB)
테스트 6 〉	통과 (0.57ms, 10.5MB)
테스트 7 〉	통과 (1.83ms, 10.6MB)
테스트 8 〉	통과 (3.64ms, 10.8MB)
테스트 9 〉	통과 (4.86ms, 11.2MB)
테스트 10 〉	통과 (5.10ms, 11.4MB)

• 깔끔하네.
  • 나도 이렇게 해볼걸...

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 〉	통과 (0.03ms, 10.2MB)
테스트 2 〉	통과 (0.06ms, 10.2MB)
테스트 3 〉	통과 (0.18ms, 10.2MB)
테스트 4 〉	통과 (0.98ms, 10.4MB)
테스트 5 〉	통과 (4.18ms, 10.4MB)
테스트 6 〉	통과 (9.66ms, 10.2MB)
테스트 7 〉	통과 (51.06ms, 10.3MB)
테스트 8 〉	통과 (111.27ms, 10.3MB)
테스트 9 〉	통과 (151.06ms, 10.7MB)
테스트 10 〉	통과 (152.25ms, 10.6MB)