할 수 있다는 신념, 하면 된다는 생각

설명

0과 1로 구성된 길이가 N인 수열이 주어집니다. 여러분은 이 수열에서 최대 k번을 0을 1로 변경할 수 있습니다. 여러분이 최대 k번의 변경을 통해 이 수열에서 1로만 구성된 최대 길이의 연속부분수열을 찾는 프로그램을 작성하세요.

만약 길이가 길이가 14인 다음과 같은 수열이 주어지고 k=2라면

1 1 0 0 1 1 0 1 1 0 1 1 0 1

여러분이 만들 수 있는 1이 연속된 연속부분수열은

이며 그 길이는 8입니다.

 

입력

첫 번째 줄에 수열의 길이인 자연수 N(5<=N<100,000)이 주어집니다.

두 번째 줄에 N길이의 0과 1로 구성된 수열이 주어집니다.

 

출력

첫 줄에 최대 길이를 출력하세요.

 

예시 입력 1 

14 2
1 1 0 0 1 1 0 1 1 0 1 1 0 1

 

예시 출력 1

8

접근 방법

입력 자연수 N의 크기가 100,000까지 있는 것과, 배열 하나를 전체 순회하는 경우를 생각하면 two pointer 방법으로 문제를 해결하는 것이 좋다. 이중 for문을 써서 O(n^2)의 시간 복잡도 보다, O(n)이 훨씬 빠르기 때문이다.

그리고 슬라이딩 윈도우(sliding window)를 통해, 두 개의 포인터가 가르킨 부분의 겹치는 영역의 길이를 구하여 답을 도출한다.

1. lt, rt를 어떻게 순회할지 지정하고, 최대 길이를 rt - lt + 1로 두어 answer의 값을 구한다.

2. rt가 순회한 곳의 배열 값이 0이라면 무조건 1로 바꾼다고 생각한다. 그리고 cnt를 1씩 증가한다.

이때, cnt가 k보다 클 때는 while문을 통해 배열값이 0이라면 cnt를 감소하고 lt를 증가한다.

만약 배열값이 1이라면 cnt는 유지한 채로 lt를 증가하여 왼쪽의 포인터가 오른쪽으로 가는 것을 구현한다.

import java.util.*;

class Main{
	public int solution(int n, int k, int[] a) {
		
		int answer=0, cnt = 0, lt = 0;
		for(int rt = 0; rt < n; rt++) {
			if(a[rt] == 0) cnt++;
			while(cnt > k) {
				if(a[lt] == 0) cnt--;
				lt++;
			}
			answer = Math.max(answer, rt - lt + 1);
		}
		
		return answer;
	}
	
	public static void main(String args[]) {
		
		Main T = new Main();
		
		Scanner sc = new Scanner(System.in);
		
		int n = sc.nextInt();
		int k = sc.nextInt();
		int[] A = new int[n];
		for(int i = 0; i < n; i++) {
			A[i] = sc.nextInt();
		}
		
		System.out.println(T.solution(n, k, A));
		
	}		
}

Key Point

문제에서 주어진 0을 1로 바꾼다고 했는데, 굳이 바꾸는 그 부분을 구현할 필요는 없다.

배열의 원소를 0에서 1로 바꾸는 과정을 구현하지 않고도, 투 포인터와 슬라이딩 윈도우를 통해 원하는 값을 도출할 수 있다.

이 글의 문제는 인프런 강의에서 참고하였습니다.

https://www.inflearn.com/course/%EC%9E%90%EB%B0%94-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EB%AC%B8%EC%A0%9C%ED%92%80%EC%9D%B4-%EC%BD%94%ED%85%8C%EB%8C%80%EB%B9%84/dashboard