DOJ logoDOJ
問題
最近追加された問題保存した問題Workbooks
カテゴリDLCコンテストグループチーム掲示板
ランキング
正解数ランキングストリークランキングDOJ Powerランキング
提出状況
問題募集ログイン新規登録
DOJ logoDOJ

OI形式のサブタスク採点、Eloレーティング、Discord連携を備えたオンラインジャッジです。

問題
問題一覧カテゴリ
コミュニティ
コンテストランキング掲示板お知らせ外部のコンテストを開催するガイド
アカウント
ログイン新規登録ジャッジ状態
ポリシー
利用規約DLCの利用規則プライバシーAPI 文書言語ランタイムコンテストの順位報酬レーティングとパフォーマンス
© 2026 DOJ
All rights reserved
解説

DOM Tree

問題に戻る

解説

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

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

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

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

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

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

Solution written by GPT5.6