문제
composite 패턴은 단일 객체와 객체들의 그룹을 같은 방식으로 다룹니다. 폴더의 크기는 자기 자신의 파일 크기와 그 안에 들어 있는 모든 것의 크기를 더한 값이며, 얼마나 깊이 들어 있든 같습니다.
0부터 n − 1까지 번호가 매겨진 n개의 항목이 트리를 이룹니다. parents[i]는 항목 i를 포함하는 폴더이며, 루트(정확히 하나의 항목)는 -1입니다. sizes[i]는 항목 i 자신의 내용 크기입니다.
composite_folder_sizes(parents, sizes)를 구현하세요.
Input
parents: 각 항목의 부모.
sizes: 각 항목의 자기 자신의 크기.
Output
각 항목에 대해 총 크기를 반환하세요: 자기 자신의 크기와 모든 자식들의 총합입니다.
제약 조건
1 ≤ n ≤ 100,000
0 ≤ sizes[i] ≤ 10^9; parents는 하나의 트리를 이룸
예시
입력:
sizes = [1, 2, 3, 4]
parents = [-1, 0, 0, 1]
예상 출력:
expected = [10, 6, 3, 4]입력:
std::vector<long long> sizes = {1, 2, 3, 4};
std::vector<long long> parents = {-1, 0, 0, 1};
예상 출력:
std::vector<long long> expected = {10, 6, 3, 4};입력:
long[] sizes = new long[] {1, 2, 3, 4};
long[] parents = new long[] {-1, 0, 0, 1};
예상 출력:
long[] expected = new long[] {10, 6, 3, 4};설명
항목 3(크기 4)은 항목 1 안에 있으므로, 항목 1의 총합은 2 + 4 = 6입니다. 루트는 항목 1과 2를 포함합니다: 1 + 6 + 3 = 10. 결과: [10, 6, 3, 4].
입력:
sizes = [5, 0, 7]
parents = [1, -1, 1]
예상 출력:
expected = [5, 12, 7]입력:
std::vector<long long> sizes = {5, 0, 7};
std::vector<long long> parents = {1, -1, 1};
예상 출력:
std::vector<long long> expected = {5, 12, 7};입력:
long[] sizes = new long[] {5, 0, 7};
long[] parents = new long[] {1, -1, 1};
예상 출력:
long[] expected = new long[] {5, 12, 7};설명
루트는 자기 자신의 내용이 없는 항목 1이며, 항목 0과 2를 포함합니다: 0 + 5 + 7 = 12.
접근 방법
먼저 스스로 풀어 본 뒤 힌트를 하나씩 열어 보세요.
힌트 1
폴더의 합계는 자기 크기와 자식 합계의 합입니다.
힌트 2
부모보다 자식을 먼저 처리하세요. 예를 들어 깊이가 깊은 순서로 처리합니다.
힌트 3
긴 사슬에서 깊은 재귀는 피하세요. 명시적인 스택이나 순서가 더 안전합니다.
예상 복잡도
시간 O(n), 추가 공간 O(n)
참고 자료
이 문제는 CodeUtility에 맞게 수정되었습니다. 위의 설명과 제한 조건을 따르세요.