2250. 트리의 높이와 너비#

관찰#

문제는
이진 트리의 각 레벨의 너비 중 최대값을 구하는 것이다.

설명에 있던 예시에서 빠르게 힌트를 얻을 수 있었는데,
전위 순회를 활용하면 모든 노드의 위치와 레벨을 함께 파악할 수 있다는 것이 핵심이었다.

순회를 진행하며 각 레벨마다 노드의 위치에 대한 최소값과 최대값을 기록해 두고,
순회가 끝난 뒤 각 레벨에 대해 최대값 - 최소값 + 1을 계산하면 해당 레벨의 너비를 구할 수 있다.

이 중 큰 값을 선택하면 문제에서 요구하는 답이 된다.

해당 문제의 조건은 $1 \le N \le 10{,}000$ 이므로,
최악의 경우 $$ O(N^2) $$ 수준의 풀이도 통과가 가능해 보였다.

다만 관찰에서 도출한 방식대로 구현하면,
트리 순회: $$ O(N) $$
레벨별 너비 계산: $$ O(log_2 N) $$
이므로, 전체 시간 복잡도는
$$ O(N) $$ 수준으로 충분히 해결할 수 있었다.

그래서 이 문제에서는 성능 최적화보다는
논리의 정확성과 구현의 안정성에 더 집중했다.

해당 문제에서, 루트 노드에 대한 설명이 없었으나,
루트 노드를 1로 가정해 문제를 풀이하다가 WA를 받았다.

이를 해결하기 위해 노드를 구성한 후,
참조되지 않은 노드를 트리의 루트로 하는 코드를 추가해 문제를 해결했다.