DOM Tree

각 노드의 HTML 표현은 정의 그대로 DFS 순서로 만들 수 있다. 다만 트리의 깊이가 $N$까지 커질 수 있으므로, 전체 제약에서는 재귀 호출 대신 명시적인 스택을 사용하면 안전하다.

스택에는 $(v,\mathrm{state})$를 저장한다. $\mathrm{state}=0$은 노드에 처음 들어가는 사건, $\mathrm{state}=1$은 태그 노드의 모든 자식을 처리한 뒤 빠져나오는 사건이라고 하자.

노드 $v$에 처음 들어갈 때 다음과 같이 처리한다.

• 텍스트 노드라면 문자열을 결과에 그대로 붙인다.
• 태그 노드라면 여는 태그를 붙이고, $(v,1)$을 스택에 넣는다. 그 뒤 자식들을 역순으로 스택에 넣는다.

스택은 마지막에 넣은 원소부터 처리하므로 자식들을 역순으로 넣으면 실제 방문 순서는 입력에서 주어진 순서가 된다. $(v,1)$을 꺼낼 때는 닫는 태그를 붙인다.

모든 테스트 케이스에서 노드 수의 합을 $S$, 출력 문자열 길이의 합을 $L$이라 하자. 각 노드와 출력 문자를 상수 번 처리하므로 시간 복잡도는 $O(S+L)$이다. 한 테스트 케이스를 처리하는 데 필요한 메모리는 $O(N+L)$이다.

Solution written by GPT5.6