회의실의 마지막 칸막이

문제

한 건물의 넓은 회의실에 이동식 칸막이를 설치하려 한다. 처음에는 회의실이 하나이며, 관리자는 현재 존재하는 공간 하나를 골라 칸막이로 두 공간으로 나누는 작업을 반복한다. 나뉜 두 공간에는 도면을 기준으로 왼쪽과 오른쪽이라는 이름을 붙인다. 이미 나눈 공간 자체는 더 이상 하나의 회의실로 사용하지 않으며, 그 안에서 최종적으로 남은 공간들만 회의실로 사용한다. 칸막이를 하나도 설치하지 않았다면 처음 공간이 그대로 최종 회의실이다. 관리자는 완성된 배치를 문자열로 기록했다. 어떤 공간을 더 나누지 않았다면 그 공간의 기록은 문자 0 하나다. 어떤 공간을 두 공간으로 나누었다면 그 공간의 기록은 문자 1, 왼쪽 공간의 기록, 오른쪽 공간의 기록을 차례로 이어 붙인 문자열이다. 이 규칙은 나뉜 공간 안에서도 똑같이 적용된다. 따라서 문자 1 바로 다음의 한 문자만으로 왼쪽 공간의 기록이 끝난다고 판단해서는 안 된다. 왼쪽 공간이 다시 나뉘었다면 그 안의 모든 기록이 먼저 나온 뒤 오른쪽 공간의 기록이 시작된다. 입력으로 주어지는 문자열은 반드시 이 규칙에 따라 처음 공간 전체를 기록한 올바른 문자열이다. 최종 회의실의 분할 깊이는 처음 공간에서 그 회의실에 이르기까지 공간을 나눈 횟수다. 처음 공간의 깊이는 0이며, 어떤 공간을 나누어 얻은 두 공간의 깊이는 각각 원래 공간의 깊이보다 1 크다. 관리자는 칸막이가 여러 겹 이어진 위치를 확인하기 위해 최종 회의실 중 가장 큰 분할 깊이와 그 깊이를 가진 회의실의 수를 알고 싶다. 가장 깊은 회의실이 여러 개라면 모두 센다. 주어진 기록을 해석하여 이 두 값을 구하는 프로그램을 작성한다.

입력

첫째 줄에 배치 기록을 나타내는 문자열 S가 주어진다. S는 문자 0과 1로만 이루어지며, 길이는 1 이상 99,999 이하인 정수다. S는 지문에 정의된 규칙으로 만든 올바른 기록이다. 별도의 공백은 주어지지 않는다.

출력

최종 회의실의 가장 큰 분할 깊이와 그 깊이를 가진 회의실의 수를 정수로 공백 하나를 사이에 두고 출력한다. 최종 회의실은 항상 하나 이상 존재한다. 칸막이가 없다면 0 1을 출력한다.

0

0 1

11000

2 2

111000100

3 2

출처: Devin.KR 자체 제작