BOJ 14057. Towers
문제 해석
높이가 모두 다른 건물 \(N\)채가 일렬로 서 있는데 여기에 탑을 세우려고 한다. 탑의 높이도 모든 건물의 높이와 다름이 보장된다. 건물의 꼭대기에서 오른쪽으로 수평선을 그었을 때 다른 건물에 막히지 않고 탑에 닿으면 해당 건물이 탑에서 “보인다”고 하자. 탑의 높이가 주어질 때 탑의 위치를 잘 정해서 탑에서 보이는 건물 수의 최댓값을 구하는 쿼리를 \(K\)번 처리해야 한다.
접근
쿼리가 한 번뿐이라면, 왼쪽부터 차례로 건물 높이를 보면서 monotone stack을 관리해 \(\mathcal{O}(N)\)에 풀 수 있다. 하지만 쿼리 \(K\)번을 \(\mathcal{O}(KN)\)에 처리할 수는 없는 노릇이므로, 이 monotone stack의 history를 잘 저장해서 \(K\)번의 쿼리 동안 재활용할 수단이 필요하다.
아이디어는 stack top의 움직임을 tree로 형상화하는 것이다. 최초에 stack이 빈 상태를 root 노드로 놓고, push를 하면 현재 노드에 해당 값으로 새로운 자식을 만들면서 내려가고, pop을 하면 부모로 올라온다. 이렇게 tree를 만들고 나면, 탑의 높이가 \(t\)일 때의 답은 \(t\)보다 작은 값을 가진 노드들의 height 중 최댓값이 된다:
\[Ans(t) = \max_{v.val < t} hei(v).\]여기서 \(hei(v)\)는 \(v\)가 leaf이면 \(1\), 아니면 \(v\)의 자식 \(w\)에 대하여 \(1 + \max_{w} hei(w)\)로 정의한다.
DFS를 돌아 \(hei\) 값들을 전부 구한 후, 건물 높이를 key로 하여 오름차순 정렬하고 prefix max를 취해 놓으면 탑의 높이를 받았을 때 답을 binary search로 구할 수 있으므로, 전체 \(\mathcal{O}((N+K)\log N)\) 시간에 해결된다. 밑에 링크한 코드에서는 편의상 stack에 건물의 높이 대신 등수(몇 번째로 낮은지, \(1\) 이상 \(N\) 이하)를 넣어서 tree의 노드(루트 제외)들이 \(1\)부터 \(N\)까지의 값을 가지도록 했다.