코딩테스트 연습> 그래프 > 순위

 

<문제링크: programmers.co.kr/learn/courses/30/lessons/49191>

코딩테스트 연습 - 순위

 

문제설명: results 배열 안에 A,B 두 선수가 리스트로 담겨있고, A>B 앞에있는 숫자(A)가 뒤에오는 숫자(B)를 이겼다는 의미이다.

 

예제로 나와있는 results의 경우 [[4, 3], [4, 2], [3, 2], [1, 2], [2, 5]] 이므로,

 

4 > 3

4 > 2

3 > 2

1 > 2

2> 5

 

이고 이를 다시 정리해본다면

 

4 > 3 > 2

4 > 2          >  5

1 > 2   

 

의 구조로 살펴볼 수 있다.

 

즉 win과 lose 딕셔너리를 생성한 다음 아래와 같은 구조로 값을 저장한다:

1. win에는 나(Key): 나에게 진사람들(Value)

2. lose에는 나(Key): 나를 이긴사람들(Value)

 

[1차 시도]

win = {x: [] for x in range(1, n + 1)}
lose = {x: [] for x in range(1, n + 1)}

 

먼저 모든 선수를 저장하기 위한 n 개의 key를 만들어주고 각각 빈 리스트를 value로 저장한다.

for winner, loser in results:     # winner = A, loser = B
    
    if loser not in win[winner]:
        win[winner].append(loser)
    
    if winner not in lose[loser]:
        lose[loser].append(winner)

 

1) results 안에는 각가 A,B가 한 쌍씩 들어있으므로, A를 winner로 B를 loser로 이름하고,

2) 중복을 방지하기 위해 loser가 win[A선수]에게 진 사람들 중 포함이 안되어 있다면 append로 포함하기

3) 마찬가지로 winner가 lose[B선수]를 이긴 사람들 중 포함이 안되어 있다면 append로 포함하기

 

win, lose print 결과

 

위와 같은 구조로 win과 lose를 준비했다면, 이제

 

4 > 3 > 2

4 > 2          >  5

1 > 2   

 

와 같은 형태로 다시 정리해줄 필요가 있다.

위에서는 win[4]에는 results에 있는 3과 2만 포함이 되어 있지만, win[2]가 5를 포함(2>5) 하고 있으므로

5 또한 4에 포함될 수 있다는 의미이다. 따라서 win[4]에는 [3,2,5]까지 포함하도록 해주면 된다.

 

마찬가지로 현재 lose[5] 리스트 안에 있는 2를 이긴 선수들, 즉 lose[2]가 가지고 있는 숫자들(2를 이긴 선수들)이

5 또한 이기는 선수들이므로 lose[5]에 추가해주면 된다.

 

1) for i in range(1, n + 1):   

2)    for winner in lose[i]:    # i=2, winner = 4,3,1
          for j in win[i]:      # win[2], j=5 
                
              if j not in win[winner]:   # win[4], win[3], win[1]에 5가 없으므로
                  win[winner].append(j)  # 5 추가하기


3)    for loser in win[i]:     # i=2, loser = 5 
          for j in lose[i]:    # lose[2], j = 4,3,1
        
              if j not in lose[loser]:   # lose[5]에 4,3,1이 없으므로
                  lose[loser].append(j)  # 4,3,1 추가하기
                
     

1) 선수 n명만큼 돌면서,

 

2) lose[선수]가 포함하는 나를 이긴 사람들(winner) 중,

lose[2] => winner: 4,3,1

 

4 > 3 > 2

4 > 2          >  5

1 > 2   

 

내가 이긴 사람들을 자신의 win에 포함하고 있지 않다면,

win[2] => j: 5

 

4 > 3 > 2

4 > 2          >  5

1 > 2   

 

밑줄 친 선수들의 win 목록(자신이 이긴 사람들)에 내가 이긴사람들(5)을 추가해주는 것이다.

 

 

3) 마찬가지로 win[선수]가 포함하는 내가 이긴 사람들(loser) 중

win[2] => loser : 5

 

나를 이긴 사람들

lose[2] => j: 4,3,1 을 자신이 진 사람들lose[5]에 포함하고 있지 않다면,

 

4 > 3 > 2

4 > 2          >  5

1 > 2   

 

lose[5] => 2 + (4,3,1)

 

lose[5]에 자신을 이긴 사람(2)의 또 이긴 사람들을 추가해주는 것이다. 

 

win, lose print 결과

 

여기까지 완료했다면 마지막으로, win과 lose에 있는 선수들의 Key 값을 더해주어 순위가 확정된 선수를 선별할 수 있다.

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

 

i = 2번 선수의 경우

 

win[2]에 5 1개 + lose[2]에 4,3,1 3개를 포함하고 있으므로

4,3,1 > 2 > 5 의 순서로 4등의 순위가 정해진 것이다.

 

따라서 전체 선수 n명 중 자기 자신을 제외한 n-1명이

자신이 이긴 선수(win)와 자신을 이긴 선수(lose)의 합과 일치하다면 순위를 매길 수 있다.

 

i = 5번 선수의 경우

 

win[5]에 0개 + lose[5]에 2,4,3,1 4개를 포함하고 있으므로

4,3,1 > 2 > 5 의 순서로 5등의 순위가 정해진 것이다.

 

 

채첨결과: 정확성과 효율성 테스트 모두 잘 통과하지만 시간을 더 줄일 수 있는 다른 방법을 적용해봤다.

 

 

 

[2차 시도]

리스트를 사용하지 않고 set()을 사용하여 중복을 방지하고,

딕셔너리 리스트에 append가 아니라 update를 하여 중복 없이 추가하도록 했다.

 

 

채첨결과: 시간이 많이 단축된 것을 확인할 수 있었다.