[프로그래머스] 순위

 

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

코딩테스트 연습 - 순위

 

 

< 문제 설명 >

results는 선수의 번호를 두개씩 담은 배열들이 들어있다.

[4, 3]일 경우에 4번선수가 3번선수를 이겼다는 의미가 된다.

이때 정확하게 순위를 매길 수 있는 선수의 수를 리턴하면 된다.

경기 결과에 모순은 없음.

 

 

< 문제 이해 >

어떤 선수를 이긴 선수는 그 어떤 선수에게 진 선수를 무조건 이긴다.

또, 어떤 선수에게 진 선수는 그 선수를 이긴 선수에게 무조건 진다.

이 두개를 이용해 문제를 풀어야 한다.

 

 

< 시행 착오 >

처음엔 그냥 배열로 했다.

그랬더니 배열 안에 겹치는 숫자들이 다 들어가 있어서 시간초과가 난듯하다,,

def solution(n, results):
    answer = 0
    win = [[] for i in range(n+1)]
    lose = [[] for i in range(n+1)]
    
    for i,j in results:
        win[i].append(j)
        lose[j].append(i)

    for i in range(1,n+1):
        for w in win[i]:
            win[i] += win[w]
        for l in lose[i]:
            lose[i] += lose[l]
            
        if len(set(win[i]))+len(set(lose[i])) == n-1:
            answer+=1
        
    return answer

 

 

< 문제 풀이 >

set()으로 바꾸고 위에 코드와 똑같이 돌렸더니 

두번째 for문에서 set이 계속 바뀐다고 오류가 났다;;;

그래서 for문에 사용되는 배열과 for문 안에서 사용되는 배열을 다르게 해주었다.

def solution(n, results):
    answer = 0
    win = [set() for i in range(n+1)]
    lose = [set() for i in range(n+1)]
    
    for i,j in results:
        lose[i].add(j) # lose[i]는 i에게 진 사람. i는 j를 이김
        win[j].add(i) # win[j]는 j에게 이긴 사람. j는 i에게 짐
        
    for i in range(1,n+1):
        for l in lose[i]: 
            win[l].update(win[i]) # i에게 이겼던 사람들은 i에게 졌던 사람에게 이김
        for w in win[i]:
            lose[w].update(lose[i]) # i에게 졌던 사람들은 i에게 이겼던 사람에게 짐
            
    for i in range(1,n+1):
        if len(lose[i]) + len(win[i]) == n-1:
            answer += 1
        
    return answer