최대 길이 연속부분수열

문제

나의풀이

import java.util.*;

class Main {
	public int solution(int n,int k, int[] arr) {
			int answer = Integer.MIN_VALUE;
			for(int start=0; start<n; start++) {
				int cnt = 0;
				int change = k; //변경권
				int end = start;
				
				while(change >= 0 && end < n) {
					if(change != 0 && arr[end] == 0) {change--; cnt++; end++;}
					else if(arr[end] == 1) {cnt++; end++;} 
					else {break;}
				}
				
				answer = Math.max(answer, cnt);
			}
			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.println(T.solution(n,k,arr));
	}
	
}

++ 다른풀이

import java.util.*;

class Main {
	public int solution(int n,int k, int[] arr) {
			int answer = Integer.MIN_VALUE;
			for(int start=0; start<n; start++) {
				int cnt = 0;
				int 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.println(T.solution(n,k,arr));
	}
	
}

풀이방법

1. 나는 start를 고정시켜두고
   while문(변경가능횟수k가 초과됐음에도 0을 만나면 종료)을 돌려서
   1을 만나면 end,cnt(길이)를 증가시켰다.
   만약, k<0인데 0을 만난다면 break;되고 cnt까지가 최대길이이다.
   answer에는 최대길이를 담아서 for문이 모두 종료되면 최대길이값이 나온다.

2. lt가 rt를 따라가면서 rt는 0을 만나면 1로 바꾸고 lt는 0을 만나면 바뀐1을 다시 0으로 만드는 역할을 한다.
   즉, rt가 0을 만나면 cnt(바꾼횟수)가 증가하고, lt가 0을 만나면 cnt가 감소한다.
   while문을 통해, 바꾼횟수가 k보다 많을때 lt가 0을 만나면 cnt가 감소한다.

핵심키워드

rt - lt + 1이 최대 길이라는것을 내 스스로 생각해낼수 있을정도까지 열심히 공부하고 연구하자!