크기가 n-1인 2차원 배열 adPair가 있다고 가정해 보겠습니다. 각 adPair[i]는 두 개의 요소 [ui, vi]를 담고 있으며, 이는 배열 nums에서 ui와 vi가 서로 인접해 있음을 의미합니다. nums에는 중복 없는 고유한 요소 n개가 들어 있습니다. 우리의 목표는 이 인접 정보만으로 원래의 배열 nums를 복원하는 것이며, 가능한 답이 여러 개라면 그중 아무거나 하나를 반환하면 됩니다.
예를 들어 입력이 adPair = [[3,2],[4,5],[4,3]]이라면 출력은 [2,3,4,5]가 됩니다.
해결 접근 방식
이 문제는 각 숫자 사이의 '이웃' 관계를 그래프의 인접 목록처럼 저장한 뒤, 이웃이 하나뿐인 숫자(배열의 끝점)에서 출발해 연결된 숫자를 차례대로 따라가며 배열을 완성하는 방식으로 해결할 수 있습니다. 단계별로 살펴보면 다음과 같습니다.
- 인접 목록 생성: my_map을 키마다 리스트를 저장하는 빈 맵(딕셔너리)으로 초기화합니다. adPair의 각 쌍 (a, b)에 대해 my_map[a] 끝에 b를, my_map[b] 끝에 a를 추가하여 양방향 인접 관계를 기록합니다.
- 시작점 찾기: my_map의 모든 키 a와 값 리스트 l을 확인하면서, l의 크기가 1인 항목을 찾습니다. 이웃이 하나뿐이라는 것은 해당 숫자가 배열의 양 끝 중 하나에 위치한다는 뜻입니다. 이 경우 nums를 두 요소 (a, l[0])로 초기화하고 반복문을 종료합니다.
- 배열 확장: i를 1부터 adPair의 크기 - 1까지 반복합니다. 매번 a, b := my_map[nums의 마지막 요소]로 마지막 숫자의 두 이웃을 가져온 뒤, a가 nums의 뒤에서 두 번째 요소(이미 사용된 이전 숫자)와 같다면 b를, 그렇지 않다면 a를 nums 끝에 추가합니다.
- 결과 반환: 모든 쌍을 처리한 후 nums를 반환합니다.
이 알고리즘은 각 숫자를 정확히 한 번씩 방문하므로 시간 복잡도는 O(n), 공간 복잡도 역시 O(n)입니다.
예제 코드
다음 구현을 통해 더 잘 이해해 보겠습니다 −
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]