섹션 3. Two pointers, Sliding window[효율성 : O(n^2)-->O(n)] 6. 최대 길이 연속부분수열

문제

• 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이 연속된 연속부분수열은
• 1 1 0 0 1 1 1 1 1 1 1 1
• 이며 그 길이는 8입니다.

입력

• 첫 번째 줄에 수열의 길이인 자연수 N(5<=N<100,000)이 주어집니다.
• 두 번째 줄에 N길이의 0과 1로 구성된 수열이 주어집니다.

출력

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

입출력 예제

---

풀이 과정을 정리해보자.

 

1. N과 K를 입력받고, 배열 arr[ ] 를 선언해서 값을 입력받은 후 메소드 구현으로 넘어가자.

• N : 수열의 길이
• K : 최대 변경 가능 횟수
• arr[ ] : 수열

2. result, cnt, lt를 선언하고 rt는 for문에서 선언한다.

• result : 결과값인 최대 길이를 저장할 변수
• cnt : 0을 1로 바꾼 횟수
• lt : 왼쪽 포인터 (포인터 : 메모리의 주소 값)
• rt : 오른쪽 포인터

3. rt가 0부터 N까지 도는 for문을 작성해서 arr[rt] 값이 0이면 cnt를 증가시킨다.

• cnt는 0을 1로 바꾼 횟수이다. 즉, arr[rt] 에 있는 값이 0이면 이를 1로 바꿨다는 의미로 cnt 를 증가시키는 것이다.
• 아래 이미지처럼 arr[2] 일 때 rt가 0 이므로 cnt = 1 이 되는 것이다.
• 이 때, rt 값 자체를 변경하게 되면 뒤에 작업이 복잡해지므로 cnt 값만 변경한다.

4. while문을 사용해서 cnt 가 K보다 클 때 arr[lt] 값이 0이면 cnt를 감소시키고 lt를 증가시킨다.

• cnt가 K보다 크다는건 0을 1로 바꾼 횟수가 K 값을 넘었다는 것이다.
• 지금까지 0을 1로 바꿔서 연속된 1의 길이보다 더 긴 값이 생겼다는 의미이다.
• 아래 이미지를 확인해보자.

• while문이 실행되기 전까지의 과정은 다음과 같다.

5. 이 후에는 cnt값이 3이고,  K 값인 2보다 커지므로 아래 조건들이 적용된다.

• lt가 0이고, arr[lt] 값이 1이므로 if 조건문을 타지 않고 lt 값만 증가한다.
• 위 과정이 반복되다가 lt가 2일때 arr[lt] 값이 0이므로 cnt는 1이 되고, lt는 1 증가해서 3이 된다.

6. (rt-lt)+1 식을 통해서 for문이 돌 때마다 연속된 1의 길이를 구한다.

• (rt - lt) + 1 : 최대 길이를 구하는 식

7. Math.max() 를 이용해서 최대 길이를 리턴한다.

• Math.max : 입력받은 두 개의 인자 중 작은 값을 리턴한다.

수행 결과를 확인한다.

---

해당 글은 인프런 > 자바(Java) 알고리즘 문제풀이 : 코딩테스트 대비(김태원)강의를 참고하여 작성하였습니다.