728x90
분석
1) 엣지 정보로 트리 리스트 생성
{1: [2, 3], 2: [4, 5], 3: [6], 4: [], 5: [7], 6: [8, 9, 10], 7: [], 8: [], 9: [], 10: []}
2) 리프노드에 떨어지는 숫자 갯수 카운트 리스트 생성 (leaf)
용도 : 순서 리스트 생성할 때 타겟값과 비교해서 몇바퀴 돌아야하는지 확인하기 위해
{4: 0, 7: 0, 8: 0, 9: 0, 10: 0}
3) 하위 인덱스 방향 관리 리스트 생성 (r)
용도 : 하위노드중 몇번째로 가는지 계산해서 가기 위해
{1: 0, 2: 0, 3: 0, 4: -1, 5: 0, 6: 0, 7: -1, 8: -1, 9: -1, 10: -1}
4) 리프노드 떨어지는 순서 리스트 생성 (order)
용도 : 리프노드 돌면서 떨어지는 수 계산하기 위해
[ ]
5) 리프노드 떨어지는 순서 리스트 데이터 추가
- 루트 노드인덱스에서 시작
- 방향 리스트의 값에 맞는 하위 노드 인덱스로 변경
- 새로운 방향으로 변경 (하위 노드 방향 인덱스 변경)
- 리프노드 떨어지는 순서 리스트에 탐색 노드 순서 저장
- 리프노드에 떨어지는 숫자 갯수 카운트 리스트에 리프노드 떨어진 횟수 저장
- 리프노드로 떨어질 때까지 반복
- 리프노드에 떨어진 개수 *3 < 타겟값이면, 반복해서 순서 탐색
- 리프노드에 떨어진 합 최대값 = 리프노드에 떨어진 개수 *3
- 타켓값보다 작다면 더 떨어진 거니까 반복해서 떨어뜨리려고 순서 탐색 반복
- 리프노드 떨어진 개수가 타겟값보다 크다면 -1출력
- 다른 노드의 숫자 합을 만들면서 해당 노드의 합을 만드는 방법은 없음
edges : [[1, 3], [1, 2]] target : [0, 7, 1]인 경우
1
2 3
7 1
2번 노드에 쌓인 숫자의 합을 7로 만들면서 3번 노드에 쌓인 숫자의 합을 1로 만들도록 숫자를 떨어트리는 방법은 없습니다.
6) 리프노드 떨어지는 순서 리스트 길이의 1로 초기화한 정답리스트 생성 (answer)
1로 초기화한 이유 : 떨어지는 1,2,3 중 1이 제일 작으니까 1로 초기화한 후 나중에 더해주면 됨
7) 리프노드 떨어지는 순서 리스트 길이를 거꾸로 돌면서
- 타겟값과 차이가 2보다 큰값은 3을 떨어뜨린거니까 정답리스트에 2를 더해 저장하고 타겟값에 2를 빼줌
- 타겟값과 차이가 1인 값은 2를 떨어뜨린거니까 정답리스트에 1를 더해 저장하고 타겟값에 1를 빼줌
거꾸로 돌리는 이유 : 사전 순으로 가장 빠른 경우로 저장해야하기 때문
edges : [[1, 3], [1, 2]] target : [0, 7, 3]인 경우
[3, 2, 1, 1, 3]순으로 숫자를 떨어트리거나 [1, 1, 1, 1, 2, 1, 3]순으로 숫자를 떨어트려도 target과 같게 만들 수 있지만, 가장 적은 숫자를 사용하며 그중 사전 순으로 가장 빠른 경우는 [1, 1, 3, 2, 3]입니다.
떨어뜨리는 숫자는 1,2,3인데 2, 1을 비교하는 이유 : 이미 정답리스트에 1을 떨어뜨린다는 가정으로 1로 초기화했기 때문
풀이
import math
def solution(edges, target):
n = len(target) # 노드 수
# 인접리스트
a = {i: [] for i in range(1, n + 1)}
for s, e in edges:
a[s].append(e)
# 리프노드
leaf = {}
for i in a:
if len(a[i]) == 0:
leaf[i] = 0
a[i].sort()
# 길(하위노드있으면 0 없으면 1)
r = {i: -1 for i in range(1, n + 1)}
for i in a:
if len(a[i]):
r[i] = 0
# 리프노드 가는 순서 찾기
order = []
flag = True
while flag:
i = 1
while r[i] != -1: # 리프노드일 때 까지
temp = i
i = a[i][r[i]] # 다음 노드 찾기 (하위 노드 인덱스로 변경)
r[temp]=(r[temp]+1)%len(a[temp]) # 새로운 길 설정 ( 하위노드 길 방향 인덱스 변경)
order.append(i) # 탐색노드 순서 저장
leaf[i]+=1 # 리프노드 떨어진 횟수 저장
# 123 떨어뜨려도 리프노드 target값보다 작으면 한바퀴 더시작
flag=False
for j in leaf:
if leaf[j]*3<target[j-1]: # 123 어떤거 떨어뜨려도 리프노드 떨어진거보다 target이 클때
flag=True
break
elif leaf[j]>target[j-1]:
return[-1]
answer = [1 for _ in range(len(order))]
for i in order:
target[i-1]-=1
# 가장 적은 숫자를 사용하며 그중 사전 순으로 가장 빠른 경우
for i in range(len(order)-1, -1, -1): # 뒤에서 부터 숫자 추가
if target[order[i]-1]>=2:
answer[i]+=2
target[order[i] - 1]-=2
elif target[order[i]-1] == 1:
answer[i]+=1
target[order[i] - 1]-=1
else:
continue
return answer
728x90