편의점 진열대의 이어진 빈칸

문제

한 편의점의 진열대에는 상품을 놓는 칸이 왼쪽부터 오른쪽으로 일렬로 늘어서 있다. 직원은 새 상품의 안내판을 설치하기 위해, 현재 비어 있는 칸이 가장 길게 이어지는 구간을 찾으려고 한다. 상품이 놓여 있는 칸은 옮길 수 없으며, 안내판을 설치하는 구간에 상품이 있는 칸을 포함할 수도 없다. 진열대의 상태는 길이가 N인 문자열 S로 주어진다. 각 문자는 진열대의 칸 하나를 나타낸다. 대문자 O는 해당 칸이 비어 있음을 뜻하고, 대문자 X는 상품이 놓여 있음을 뜻한다. 문자열의 첫 번째 문자가 가장 왼쪽 칸이며, 칸 번호는 왼쪽부터 1번, 2번, …, N번이다. 문자 O는 숫자 0이 아닌 영문 대문자다. 선택할 수 있는 구간은 하나 이상의 칸으로 이루어져야 하며, 구간 안의 모든 문자가 O여야 한다. 또한 선택한 칸들은 진열대에서 서로 연속해야 한다. 중간에 X가 하나라도 있으면 그 양쪽의 빈칸을 하나의 구간으로 묶을 수 없다. 진열대의 맨 왼쪽과 맨 오른쪽은 서로 이어져 있지 않다. 직원은 선택할 수 있는 구간 중 칸 수가 가장 많은 구간을 고른다. 같은 길이의 구간이 여러 개 있다면 시작 칸 번호가 가장 작은 구간을 고른다. 출력할 값은 고른 구간의 칸 수와 시작 칸 번호다. 끝 칸 번호나 문자열 자체는 출력하지 않는다. N은 1 이상 1,000 이하의 정수이며, 문자열에는 O와 X만 등장한다. 모든 칸이 비어 있을 수도 있고, 빈칸이 하나도 없을 수도 있다. 빈칸이 하나도 없어 선택 가능한 구간이 없다면 구간의 칸 수와 시작 칸 번호를 모두 0으로 출력한다. 주어진 진열대 상태에서 이 규칙에 따라 안내판을 설치할 구간을 구한다.

입력

첫째 줄에 진열대의 칸 수 N이 주어진다. (1 ≤ N ≤ 1,000)
둘째 줄에 길이가 정확히 N이고 영문 대문자 O와 X로만 이루어진 문자열 S가 주어진다.

출력

선택한 구간의 칸 수와 시작 칸 번호를 공백으로 구분하여 출력한다. 선택 가능한 구간이 없다면 0 0을 출력한다.

12
XOOOXOOOXOOX

3 2

5
XXXXX

0 0

7
OXOOOOO

5 3

출처: Devin.KR 자체 제작