나란히 비어 있는 충전 자리

문제

전기차 충전소의 한쪽 벽을 따라 충전 자리가 N개 나란히 놓여 있다. 각 자리에는 왼쪽부터 차례로 1번부터 N번까지 번호가 붙어 있다. 관리자는 함께 도착할 차량들을 가까이 세울 수 있도록, 지금 바로 사용할 수 있는 자리가 연속해서 이어진 구간 하나를 안내하려 한다. 충전소의 상태는 길이가 N인 문자열 S로 주어진다. 문자 0은 현재 비어 있고 정상적으로 사용할 수 있는 자리를 뜻한다. 문자 1은 다른 차량이 사용하고 있는 자리를 뜻하며, 문자 X는 점검 중이어서 사용할 수 없는 자리를 뜻한다. 안내 구간에 포함되는 모든 자리는 반드시 0이어야 한다. 사용 중인 자리와 점검 중인 자리는 모두 구간을 끊으며, 그 자리를 건너뛰어 양쪽의 빈 자리를 하나의 구간으로 합칠 수 없다. 구간은 시작 번호 L과 끝 번호 R로 나타낸다. 이 구간에는 L번부터 R번까지의 모든 자리가 포함되며 길이는 R-L+1이다. 관리자는 안내할 수 있는 구간 중 길이가 가장 긴 구간을 선택한다. 가장 긴 구간이 여러 개라면 시작 번호 L이 가장 작은 구간을 선택한다. 길이가 같고 시작 번호도 같으면 끝 번호가 자동으로 같으므로 추가적인 동점 규칙은 필요하지 않다. 예를 들어 연속한 세 자리가 모두 비어 있다면 그중 두 자리만 안내하는 것도 규칙상 가능하지만, 다른 더 긴 구간이 없다면 세 자리 전체를 안내해야 한다. 문자열의 첫 자리나 마지막 자리도 구간에 포함될 수 있으며, 충전 자리는 원형으로 이어져 있지 않으므로 N번과 1번은 서로 이웃하지 않는다. 주어진 상태는 안내가 끝날 때까지 변하지 않는다. 선택해야 하는 구간의 시작 번호와 끝 번호를 구한다. 사용할 수 있는 자리가 하나도 없다면 -1을 출력한다.

입력

첫째 줄에 충전 자리 수인 정수 N이 주어진다. (1 ≤ N ≤ 100,000)
둘째 줄에 길이가 정확히 N인 문자열 S가 주어진다. S는 문자 0, 1, X로만 이루어지며 공백을 포함하지 않는다.

출력

선택한 구간의 시작 번호 L과 끝 번호 R을 공백으로 구분하여 한 줄에 출력한다. 사용할 수 있는 자리가 없으면 -1만 출력한다.

12
1000X0001100

2 4

4
1XX1

-1

5
00000

1 5

출처: Devin.KR 자체 제작