[알고리즘] Two pointers, Sliding window(6) : 최대 길이 연속부분 수열(JAVA)

ho's·2022년 5월 26일
0

🎪 최대 길이 연속부분 수열(JAVA)

👔 문제

👖풀이

위 문제는 rt의 값이 lt를 따라가는 식으로 작성을 해야한다.

  • lt, rt의 값을 0으로 고정시켜주고, rt가 0을 만나면 1로 바꾸어 주고 cnt++;를 해준다.
  • answer는 cnt>K 가 성립이 될때, rt-lt+1 을 한 값을 넣어준다.
int answer = 0,cnt=0, lt=0;
for(int rt=0;rt<n;rt++){
	if(arr[rt] == 0){
    	
        if(arr[rt] == 0)
        	cnt++;
        while(cnt>k){
        	if(arr[lt] == 0) cnt--;
            lt++;
        }
        answer = Math.max(answer, rt-lt+1);
    }
    return answer;
}

🧦 소스코드

import java.util.Scanner;

public class Main30 {
    public int solution(int n, int k, int[] arr){

        int answer = 0, cnt =0, lt =0;

        for(int rt =0; rt<n;rt++){
            if(arr[rt] == 0)
                cnt++;

            while(cnt>k){
                if(arr[lt] == 0) cnt--;
                lt++;
            }
            answer = Math.max(answer, rt-lt+1);
        }
        return answer;
    }

    public static void main(String[] args) {
        Main30 T = new Main30();
        Scanner kb = new Scanner(System.in);
        int n = kb.nextInt();
        int k = kb.nextInt();
        int[] arr = new int[n];
        for(int i=0;i<n;i++){
            arr[i] = kb.nextInt();
        }
        System.out.print(T.solution(n,k,arr));
    }
}
profile
그래야만 한다

0개의 댓글