간단한 투포인터 문제

문제는 다음과 같다.

1은 길을, 0은 수리가 필요한 길이다.
하지만 인력과 돈은 한정되어있기에,
n개의 길만 수리할 수 있다.
이때,
1과 0으로 주어진 길과 n을 입력하면,
해당 길을 가장 길게 연결할 수 있는 출력을 구하시오.

입력 예시
111101011001001110101, 4
출력 예시
12 (맨 처음의 1111010111001)

입력 예시
10000011011101100101, 4
출력 예시
12 (7번째 1부터 뒤에서 3번째 1까지)




풀이는 다음과 같다.

    //1이 길이고 0이 못가는길
    static int twoPointer(String S, int n) {
        int[] road = new int[S.length()];

        int zero = 0; //전체 길의 0의 개수

        for(int i = 0 ; i < S.length() ; i++) {
            if(S.charAt(i) == '1') road[i] = 1;
            else {
                road[i] = 0;
                zero++;
            }
        }

        if(zero <= n) return S.length(); //고장난 길이 n보다 적다면
        //전체 길을 통과할 수 있으니.

        int num_zero = 0; //초기 세팅시 사용
        int s = 0;
        int e = 0;

        int max = 0;
        int answer = 0;

        while(true) {
            if(road[e] == 0) num_zero++;
            if(num_zero == n+1) break;
            e++;
        }

        e -= 1;

        max = e - s + 1;

        //초기 투포인터 세팅 (맨 처음 고장난 길을 n개 포함했을때의 s와 e를 세팅.)

        while(e < S.length()) { //end 포인터가 배열의 끝이 되기 전까지
            e++; //n+1개의 고장난 길을 맞닥뜨림

            while(true) {
                if(e+1 >= S.length()) break;
                if(road[e+1] == 0) break; //이제 진행할 길이 0이라면, 고장난 길의 개수가 n+2가 된다.
                //그러니까 그 전까지만 진행. n+1개의 고장난 길로 가장 긴 길을 뽑아냄.
                e++;
            }

            while(true) {
                s++;
                if(road[s-1] == 0) break; //바로 지나왔던 이전의 길이 0이라면, 고장난 길의 개수가 위의 n+1에서 하나가 빠져 n개가 된다.
            }

            //여기까지 오면 s와 e 사이에 고장난 길이 n개이고, e는 0을 만나기 전까지, s는 0의 바로 다음까지 간것.

            answer = e-s+1; //거리 구하고
            max = Math.max(max, answer); //최대 거리 길 갱신.
        }
        
        return max;
    }