Python의 인접한 쌍에서 배열을 복원하는 프로그램

각 adPair[i]에 두 개의 요소가 있는 n-1 크기의 adPair라는 2D 배열이 있다고 가정합니다. [ui, vi]는 요소 ui와 vi가 nums라는 배열에서 인접함을 나타냅니다. nums에는 n개의 고유 요소가 있습니다. 배열 번호를 찾아야 합니다. 여러 솔루션이 있는 경우 그 중 하나를 반환하십시오.

따라서 입력이 adPair =[[3,2],[4,5],[4,3]]과 같으면 출력은 [2,3,4,5]

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

• my_map :=다른 키에 대한 목록을 저장하기 위한 빈 맵
• adPair의 각 쌍(a, b)에 대해 다음을 수행합니다.
  • my_map[a] 끝에 b 삽입
  • my_map[b] 끝에 삽입
• my_map의 각 키 및 값 목록 l에 대해 다음을 수행합니다.
  • l의 크기가 1과 같으면
    • nums :=두 개의 요소(a, l[0])가 있는 목록
    • 루프에서 나오다
• 범위 1에서 adPair - 1의 크기에 있는 i에 대해
  • a, b :=my_map[숫자의 마지막 요소]
  • a가 nums의 두 번째 마지막 요소와 같으면
    • 숫자 끝에 b 삽입
  • 그렇지 않으면
    • 숫자 끝에 삽입
• 반환 번호

예시

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

from collections import defaultdict
def solve(adPair):
   my_map = defaultdict(list)
   for a, b in adPair:
      my_map[a].append(b)
      my_map[b].append(a)

   for a, l in my_map.items():
      if len(l) == 1:
         nums = [a, l[0]]
         break
   for i in range(1, len(adPair)):
      a, b = my_map[nums[-1]]

      if a == nums[-2]:
         nums.append(b)
      else:
         nums.append(a)

   return nums

adPair = [[3,2],[4,5],[4,3]]
print(solve(adPair))

입력

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

출력

[2, 3, 4, 5]