[문제풀이] 03-06. 최대 길이 연속 부분 수열

인프런, 자바(Java) 알고리즘 문제풀이

Two pointers, Sliding window - 0306. 최대 길이 연속 부분 수열

🗒️ 문제

🎈 나의 풀이

	private static int solution(int n, int m, String[] strArr) {
        int answer = 0, l = 0, r = 0, zero = 0, len = 0;

        while(r < n && l < n) {
            if(zero <= m) {
                answer = Math.max(answer, len);
                if(strArr[r].equals("0")) zero++;
                len++;
                r++;
            } else {
                if(strArr[l].equals("0")) zero--;
                len--;
                l++;
            }
        }

        return answer;
    }
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String[] strArr = sc.nextLine().split(" ");
        int n = Integer.parseInt(strArr[0]);
        int m = Integer.parseInt(strArr[1]);
        strArr = sc.nextLine().split(" ");

        System.out.println(solution(n, m, strArr));
    }

🖍️ 강의 풀이

    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){
		Main T = new Main();
		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));
	}

💬 짚어가기

해당 문제는 앞선 연속 부분 수열 문제에서 조건이 하나 더 추가된 문제이다.
기본적인 틀은 two pointers와 sliding windw를 이용해 배열을 순회하도록 한다.

핵심은 window안에 0의 갯수가 2 이하가 되도록 유지하는 것이다. 해당 조건을 만족하도록
두 개의 pointer를 움직여주면 된다.