시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 1485 670 502 47.628%

문제

이진 검색 트리는 다음과 같은 세 가지 조건을 만족하는 이진 트리이다.

  • 노드의 왼쪽 서브트리에 있는 모든 노드의 키는 노드의 키보다 작다.
  • 노드의 오른쪽 서브트리에 있는 모든 노드의 키는 노드의 키보다 크다.
  • 왼쪽, 오른쪽 서브트리도 이진 검색 트리이다.

전위 순회 (루트-왼쪽-오른쪽)은 루트를 방문하고, 왼쪽 서브트리, 오른쪽 서브 트리를 순서대로 방문하면서 노드의 키를 출력한다. 후위 순회 (왼쪽-오른쪽-루트)는 왼쪽 서브트리, 오른쪽 서브트리, 루트 노드 순서대로 키를 출력한다. 예를 들어, 위의 이진 검색 트리의 전위 순회 결과는 50 30 24 5 28 45 98 52 60 이고, 후위 순회 결과는 5 28 24 45 30 60 52 98 50 이다.

이진 검색 트리를 전위 순회한 결과가 주어졌을 때, 이 트리를 후위 순회한 결과를 구하는 프로그램을 작성하시오.

입력

트리를 전위 순회한 결과가 주어진다. 노드에 들어있는 키의 값은 106보다 작은 양의 정수이다. 모든 값은 한 줄에 하나씩 주어지며, 노드의 수는 10,000개 이하이다. 같은 키를 가지는 노드는 없다.

출력

입력으로 주어진 이진 검색 트리를 후위 순회한 결과를 한 줄에 하나씩 출력한다.

예제 입력 1

50
30
24
5
28
45
98
52
60

예제 출력 1

5
28
24
45
30
60
52
98
50

힌트

W3sicHJvYmxlbV9pZCI6IjU2MzkiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWM3NzRcdWM5YzQgXHVhYzgwXHVjMGM5IFx1ZDJiOFx1YjlhYyIsImRlc2NyaXB0aW9uIjoiPHA+XHVjNzc0XHVjOWM0IFx1YWM4MFx1YzBjOSBcdWQyYjhcdWI5YWNcdWIyOTQgXHViMmU0XHVjNzRjXHVhY2ZjIFx1YWMxOVx1Yzc0MCBcdWMxMzggXHVhYzAwXHVjOWMwIFx1Yzg3MFx1YWM3NFx1Yzc0NCBcdWI5Y2NcdWM4NzFcdWQ1NThcdWIyOTQgXHVjNzc0XHVjOWM0IFx1ZDJiOFx1YjlhY1x1Yzc3NFx1YjJlNC48XC9wPlxyXG5cclxuPHVsPlxyXG5cdDxsaT5cdWIxNzhcdWI0ZGNcdWM3NTggXHVjNjdjXHVjYWJkIFx1YzExY1x1YmUwY1x1ZDJiOFx1YjlhY1x1YzVkMCBcdWM3ODhcdWIyOTQgXHViYWE4XHViNGUwIFx1YjE3OFx1YjRkY1x1Yzc1OCBcdWQwYTRcdWIyOTQgXHViMTc4XHViNGRjXHVjNzU4IFx1ZDBhNFx1YmNmNFx1YjJlNCBcdWM3OTFcdWIyZTQuPFwvbGk+XHJcblx0PGxpPlx1YjE3OFx1YjRkY1x1Yzc1OCBcdWM2MjRcdWI5NzhcdWNhYmQgXHVjMTFjXHViZTBjXHVkMmI4XHViOWFjXHVjNWQwIFx1Yzc4OFx1YjI5NCBcdWJhYThcdWI0ZTAgXHViMTc4XHViNGRjXHVjNzU4IFx1ZDBhNFx1YjI5NCBcdWIxNzhcdWI0ZGNcdWM3NTggXHVkMGE0XHViY2Y0XHViMmU0IFx1ZDA2Y1x1YjJlNC48XC9saT5cclxuXHQ8bGk+XHVjNjdjXHVjYWJkLCBcdWM2MjRcdWI5NzhcdWNhYmQgXHVjMTFjXHViZTBjXHVkMmI4XHViOWFjXHViM2M0IFx1Yzc3NFx1YzljNCBcdWFjODBcdWMwYzkgXHVkMmI4XHViOWFjXHVjNzc0XHViMmU0LjxcL2xpPlxyXG48XC91bD5cclxuXHJcbjxwPjxpbWcgYWx0PVwiXCIgc3JjPVwiXC91cGxvYWRcL2ltYWdlc1wvYnNlYXJjaHRyZWUucG5nXCIgc3R5bGU9XCJoZWlnaHQ6MjQycHg7IHdpZHRoOjQyNnB4XCIgXC8+PFwvcD5cclxuXHJcbjxwPlx1YzgwNFx1YzcwNCBcdWMyMWNcdWQ2OGMgKFx1YjhlOFx1ZDJiOC1cdWM2N2NcdWNhYmQtXHVjNjI0XHViOTc4XHVjYWJkKVx1Yzc0MCBcdWI4ZThcdWQyYjhcdWI5N2MgXHViYzI5XHViYjM4XHVkNTU4XHVhY2UwLCBcdWM2N2NcdWNhYmQgXHVjMTFjXHViZTBjXHVkMmI4XHViOWFjLCBcdWM2MjRcdWI5NzhcdWNhYmQgXHVjMTFjXHViZTBjIFx1ZDJiOFx1YjlhY1x1Yjk3YyBcdWMyMWNcdWMxMWNcdWIzMDBcdWI4NWMgXHViYzI5XHViYjM4XHVkNTU4XHViYTc0XHVjMTFjIFx1YjE3OFx1YjRkY1x1Yzc1OCBcdWQwYTRcdWI5N2MgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LiBcdWQ2YzRcdWM3MDQgXHVjMjFjXHVkNjhjIChcdWM2N2NcdWNhYmQtXHVjNjI0XHViOTc4XHVjYWJkLVx1YjhlOFx1ZDJiOClcdWIyOTQgXHVjNjdjXHVjYWJkIFx1YzExY1x1YmUwY1x1ZDJiOFx1YjlhYywgXHVjNjI0XHViOTc4XHVjYWJkIFx1YzExY1x1YmUwY1x1ZDJiOFx1YjlhYywgXHViOGU4XHVkMmI4IFx1YjE3OFx1YjRkYyBcdWMyMWNcdWMxMWNcdWIzMDBcdWI4NWMgXHVkMGE0XHViOTdjIFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC4gXHVjNjA4XHViOTdjIFx1YjRlNFx1YzViNCwgXHVjNzA0XHVjNzU4IFx1Yzc3NFx1YzljNCBcdWFjODBcdWMwYzkgXHVkMmI4XHViOWFjXHVjNzU4IFx1YzgwNFx1YzcwNCBcdWMyMWNcdWQ2OGMgXHVhY2IwXHVhY2ZjXHViMjk0IDUwIDMwIDI0IDUgMjggNDUgOTggNTIgNjAgXHVjNzc0XHVhY2UwLCBcdWQ2YzRcdWM3MDQgXHVjMjFjXHVkNjhjIFx1YWNiMFx1YWNmY1x1YjI5NCA1IDI4IDI0IDQ1IDMwIDYwIDUyIDk4IDUwIFx1Yzc3NFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjNzc0XHVjOWM0IFx1YWM4MFx1YzBjOSBcdWQyYjhcdWI5YWNcdWI5N2MgXHVjODA0XHVjNzA0IFx1YzIxY1x1ZDY4Y1x1ZDU1YyBcdWFjYjBcdWFjZmNcdWFjMDAgXHVjOGZjXHVjNWI0XHVjODRjXHVjNzQ0IFx1YjU0YywgXHVjNzc0IFx1ZDJiOFx1YjlhY1x1Yjk3YyBcdWQ2YzRcdWM3MDQgXHVjMjFjXHVkNjhjXHVkNTVjIFx1YWNiMFx1YWNmY1x1Yjk3YyBcdWFkNmNcdWQ1NThcdWIyOTQgXHVkNTA0XHViODVjXHVhZGY4XHViN2E4XHVjNzQ0IFx1Yzc5MVx1YzEzMVx1ZDU1OFx1YzJkY1x1YzYyNC48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1ZDJiOFx1YjlhY1x1Yjk3YyBcdWM4MDRcdWM3MDQgXHVjMjFjXHVkNjhjXHVkNTVjIFx1YWNiMFx1YWNmY1x1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1YjE3OFx1YjRkY1x1YzVkMCBcdWI0ZTRcdWM1YjRcdWM3ODhcdWIyOTQgXHVkMGE0XHVjNzU4IFx1YWMxMlx1Yzc0MCAxMDxzdXA+NjxcL3N1cD5cdWJjZjRcdWIyZTQgXHVjNzkxXHVjNzQwIFx1YzU5MVx1Yzc1OCBcdWM4MTVcdWMyMThcdWM3NzRcdWIyZTQuIFx1YmFhOFx1YjRlMCBcdWFjMTJcdWM3NDAgXHVkNTVjIFx1YzkwNFx1YzVkMCBcdWQ1NThcdWIwOThcdWM1MjkgXHVjOGZjXHVjNWI0XHVjOWMwXHViYTcwLCBcdWIxNzhcdWI0ZGNcdWM3NTggXHVjMjE4XHViMjk0IDEwLDAwMFx1YWMxYyBcdWM3NzRcdWQ1NThcdWM3NzRcdWIyZTQuIFx1YWMxOVx1Yzc0MCBcdWQwYTRcdWI5N2MgXHVhYzAwXHVjOWMwXHViMjk0IFx1YjE3OFx1YjRkY1x1YjI5NCBcdWM1YzZcdWIyZTQuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHVjNzg1XHViODI1XHVjNzNjXHViODVjIFx1YzhmY1x1YzViNFx1YzljNCBcdWM3NzRcdWM5YzQgXHVhYzgwXHVjMGM5IFx1ZDJiOFx1YjlhY1x1Yjk3YyBcdWQ2YzRcdWM3MDQgXHVjMjFjXHVkNjhjXHVkNTVjIFx1YWNiMFx1YWNmY1x1Yjk3YyBcdWQ1NWMgXHVjOTA0XHVjNWQwIFx1ZDU1OFx1YjA5OFx1YzUyOSBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVkNTVjXHVhZDZkXHVjNWI0In0seyJwcm9ibGVtX2lkIjoiNTYzOSIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IkJpbmFyeSBTZWFyY2ggVHJlZSIsImRlc2NyaXB0aW9uIjoiPHA+QSBiaW5hcnkgc2VhcmNoIHRyZWUgaXMgYSBiaW5hcnkgdHJlZSB0aGF0IHNhdGlzZmllcyB0aGUgZm9sbG93aW5nIHByb3BlcnRpZXM6Jm5ic3A7PFwvcD5cclxuXHJcbjx1bD5cclxuXHQ8bGk+VGhlIGxlZnQgc3VidHJlZSBvZiBhIG5vZGUgY29udGFpbnMgb25seSBub2RlcyB3aXRoIGtleXMgbGVzcyB0aGFuIHRoZSBub2RlJiMzOTtzIGtleS4mbmJzcDs8XC9saT5cclxuXHQ8bGk+VGhlIHJpZ2h0IHN1YnRyZWUgb2YgYSBub2RlIGNvbnRhaW5zIG9ubHkgbm9kZXMgd2l0aCBrZXlzIGdyZWF0ZXIgdGhhbiB0aGUgbm9kZSYjMzk7cyBrZXkuJm5ic3A7PFwvbGk+XHJcblx0PGxpPkJvdGggdGhlIGxlZnQgYW5kIHJpZ2h0IHN1YnRyZWVzIG11c3QgYWxzbyBiZSBiaW5hcnkgc2VhcmNoIHRyZWVzLiZuYnNwOzxcL2xpPlxyXG48XC91bD5cclxuXHJcbjxwPjxpbWcgYWx0PVwiXCIgc3JjPVwiXC91cGxvYWRcL2ltYWdlc1wvYnNlYXJjaHRyZWUucG5nXCIgc3R5bGU9XCJoZWlnaHQ6MjQycHg7IHdpZHRoOjQyNnB4XCIgXC8+PFwvcD5cclxuXHJcbjxwPlByZS1vcmRlciB0cmF2ZXJzYWwgKFJvb3QtTGVmdC1SaWdodCkgcHJpbnRzIG91dCB0aGUgbm9kZSZyc3F1bztzIGtleSBieSB2aXNpdGluZyB0aGUgcm9vdCBub2RlIHRoZW4gdHJhdmVyc2luZyB0aGUgbGVmdCBzdWJ0cmVlIGFuZCB0aGVuIHRyYXZlcnNpbmcgdGhlIHJpZ2h0IHN1YnRyZWUuIFBvc3Qtb3JkZXIgdHJhdmVyc2FsIChMZWZ0Jm5kYXNoO1JpZ2h0LVJvb3QpIHByaW50cyBvdXQgdGhlIGxlZnQgc3VidHJlZSBmaXJzdCBhbmQgdGhlbiByaWdodCBzdWJ0cmVlIGFuZCBmaW5hbGx5IHRoZSByb290IG5vZGUuIEZvciBleGFtcGxlLCB0aGUgcmVzdWx0cyBvZiBwcmUtb3JkZXIgdHJhdmVyc2FsIGFuZCBwb3N0LW9yZGVyIHRyYXZlcnNhbCBvZiB0aGUgYmluYXJ5IHRyZWUgc2hvd24gaW4gRmlndXJlIDEgYXJlIGFzIGZvbGxvd3M6Jm5ic3A7PFwvcD5cclxuXHJcbjx1bD5cclxuXHQ8bGk+UHJlLW9yZGVyOiA1MCAzMCAyNCA1IDI4IDQ1IDk4IDUyIDYwJm5ic3A7PFwvbGk+XHJcblx0PGxpPlBvc3Qtb3JkZXI6IDUgMjggMjQgNDUgMzAgNjAgNTIgOTggNTAmbmJzcDs8XC9saT5cclxuPFwvdWw+XHJcblxyXG48cD5HaXZlbiB0aGUgcHJlLW9yZGVyIHRyYXZlcnNhbCBvZiBhIGJpbmFyeSBzZWFyY2ggdHJlZSwgeW91IHRhc2sgaXMgdG8gZmluZCB0aGUgcG9zdC1vcmRlciB0cmF2ZXJzYWwgb2YgdGhpcyB0cmVlLjxcL3A+XHJcbiIsImlucHV0IjoiPHA+VGhlIGtleXMgb2YgYWxsIG5vZGVzIG9mIHRoZSBpbnB1dCBiaW5hcnkgc2VhcmNoIHRyZWUgYXJlIGdpdmVuIGFjY29yZGluZyB0byBwcmUtb3JkZXIgdHJhdmVyc2FsLiBFYWNoIG5vZGUgaGFzIGEga2V5IHZhbHVlIHdoaWNoIGlzIGEgcG9zaXRpdmUgaW50ZWdlciBsZXNzIHRoYW4gMTA8c3VwPjY8XC9zdXA+LiBBbGwgdmFsdWVzIGFyZSBnaXZlbiBpbiBzZXBhcmF0ZSBsaW5lcyAob25lIGludGVnZXIgcGVyIGxpbmUpLiBZb3UgY2FuIGFzc3VtZSB0aGF0IGEgYmluYXJ5IHNlYXJjaCB0cmVlIGRvZXMgbm90IGNvbnRhaW4gbW9yZSB0aGFuIDEwLDAwMCBub2RlcyBhbmQgdGhlcmUgYXJlIG5vIGR1cGxpY2F0ZSBub2Rlcy4mbmJzcDs8XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5UaGUgb3V0cHV0IGNvbnRhaW5zIHRoZSByZXN1bHQgb2YgcG9zdC1vcmRlciB0cmF2ZXJzYWwgb2YgdGhlIGlucHV0IGJpbmFyeSB0cmVlLiBQcmludCBvdXQgb25lIGtleSBwZXIgbGluZS4mbmJzcDs8XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWM2MDFcdWM1YjQifV0=