파이썬에서 불행한 친구의 수를 세는 프로그램

<시간/>

n(짝수) 다른 친구에 대한 선호도 목록이 있다고 가정합니다. 각 사람 i에 대해 선호도[i]에는 선호도 순으로 정렬된 친구 목록이 있습니다. 따라서 목록의 앞부분에 있는 친구가 목록의 뒷부분에 있는 친구보다 더 선호됩니다. 각 목록의 친구는 0에서 n-1 사이의 정수로 번호가 매겨집니다. 모든 친구는 서로 다른 쌍으로 나뉩니다. 여기서 pair[i] =[xi, yi]는 xi가 yi와 쌍을 이루고/하거나 yi가 xi와 쌍을 이루는 것을 나타냅니다. 그러나 친구 x는 x가 y와 짝을 이루고 v와 짝을 이루는 친구 u가 있으면 불행하지만 -

x는 y보다 u를 선호하고
v보다 x를 선호합니다.

불행한 친구의 수를 찾아야 합니다.

따라서 입력이 기본 설정 =[[1, 2, 3], [3, 2, 0], [3, 1, 0], [1, 2, 0]] 쌍 =[[0, 1]인 경우 , [2, 3]], 첫 번째 친구는 사람 1이 사람 0과 짝을 이루었지만 사람 0보다 사람 3을 선호하고 사람 3이 사람 2보다 사람 1을 선호하기 때문에 출력이 2가 됩니다. 그리고 친구 3은 불행합니다. 사람 3은 사람 2와 짝을 이루지만 사람 2보다 사람 1을 선호하고 사람 1은 사람 0보다 사람 3을 선호하기 때문입니다.

이 문제를 해결하기 위해 다음 단계를 따릅니다. −

graph :=그래프를 만들기 위한 인접 목록, 처음에는 비어 있음
각 쌍(s, e)에 대해 쌍으로 수행합니다.
- 기본 설정의 각 기본 설정에 대해 다음을 수행합니다.
  - pref가 end와 같으면
    - 루프에서 나오다
  - 그래프[s, pref] :=1
- 기본 설정[e]의 각 기본 설정에 대해 다음을 수행합니다.
  - pref가 start와 같으면
    - 루프에서 나오다
  - 그래프[e, pref] :=1
불행 :=0
각 쌍(s, e)에 대해 쌍으로 수행합니다.
- 그래프의 각 pref에 대해 다음을 수행합니다.
  - 그래프[pref][s]가 비어 있지 않으면
    - 불행 :=불행 + 1
    - 루프에서 나오다
- 그래프[end]의 각 pref에 대해 다음을 수행합니다.
  - 그래프[pref][e]가 비어 있지 않으면
    - 불행 :=불행 + 1
    - 루프에서 나오다
불행한 반품

예시

이해를 돕기 위해 다음 구현을 살펴보겠습니다. −

from collections import defaultdict
def solve(preferences, pairs):
   graph = defaultdict(dict)
   for start, end in pairs:
      for pref in preferences[start]:
         if pref == end:
            break
         graph[start][pref] = 1
      for pref in preferences[end]:
         if pref == start:
            break
         graph[end][pref] = 1

   unhappy = 0

   for start, end in pairs:
      for pref in graph[start]:
         if graph[pref].get(start, None):
            unhappy += 1
            break
      for pref in graph[end]:
         if graph[pref].get(end, None):
            unhappy += 1
            break
   return unhappy

preferences = [[1, 2, 3], [3, 2, 0], [3, 1, 0], [1, 2, 0]]
pairs = [[0, 1], [2, 3]]
print(solve(preferences, pairs))

입력

[[1, 2, 3], [3, 2, 0], [3, 1, 0], [1, 2, 0]], [[0, 1], [2, 3]]