트립(이진 탐색 힙) 구성

시간 제한1초메모리 제한128 MB

요약

라벨과 우선순위 쌍들이 주어질 때, 라벨에 대해서는 이진 탐색 트리이고 우선순위에 대해서는 최대 힙인 유일한 트립을 만들어 괄호 형태로 출력한다.

난이도: 보통10점 중 7점
유형: 트리, 스택, 정렬, 재귀
정답자: 아직 제출이 없습니다

문제

힙(heap) 은 각 노드에 우선순위(priority)(숫자)가 매겨진 트리로, 모든 노드의 우선순위가 그 부모 노드의 우선순위보다 작은 트리를 말한다. 따라서 루트가 트리 전체에서 가장 큰 우선순위를 가지며, 이 성질 덕분에 힙은 우선순위 큐를 구현하거나 정렬을 수행하는 데 쓰인다.

각 노드가 레이블(label) 과 우선순위 를 함께 가지며, 레이블에 대해서는 이진 탐색 트리(모든 노드의 레이블이 그 왼쪽 서브트리에 있는 모든 레이블보다 크고 오른쪽 서브트리에 있는 모든 레이블보다 작음)이면서, 동시에 우선순위에 대해서는 힙 인 이진 트리를 트립(treap) 이라고 한다.

레이블이 서로 다르고 우선순위도 서로 다른 레이블/우선순위 쌍들의 집합이 주어질 때, 이 자료를 담는 트립을 구성하여라. 레이블과 우선순위가 모두 서로 다르므로 이러한 트립은 유일하다.

입력

입력은 여러 개의 테스트 케이스로 이루어진다. 각 테스트 케이스는 정수 $n$ ( $1 \le n \le 50000$ ) 으로 시작한다. 이어서 각 노드의 레이블과 우선순위를 나타내는 $n$ 개의 쌍 $l_1/p_1, \dots, l_n/p_n$ 이 주어진다. 각 레이블은 비어 있지 않은 소문자 문자열이고, 각 우선순위는 음이 아닌 정수이다. 한 테스트 케이스 안에서 모든 레이블은 서로 다르고 모든 우선순위도 서로 다르다. 마지막 테스트 케이스 다음에는 $0$ 하나가 주어지며, 이 값은 처리하지 않는다.

출력

각 테스트 케이스마다, 주어진 노드들을 담는 트립을 한 줄에 출력한다. 트립은 (<왼쪽 서브트립><레이블>/<우선순위><오른쪽 서브트립>) 형태로 출력한다. 서브트립은 재귀적으로 같은 방식으로 출력하며, 비어 있는 서브트립은 생략한다.

예제1

예제 1

입력

7 a/7 b/6 c/5 d/4 e/3 f/2 g/1
7 a/1 b/2 c/3 d/4 e/5 f/6 g/7
7 a/3 b/6 c/4 d/7 e/2 f/5 g/1
0

예상 출력

(a/7(b/6(c/5(d/4(e/3(f/2(g/1)))))))
(((((((a/1)b/2)c/3)d/4)e/5)f/6)g/7)
(((a/3)b/6(c/4))d/7((e/2)f/5(g/1)))