설명
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로 바꾸는 과정을 구현하지 않고도, 투 포인터와 슬라이딩 윈도우를 통해 원하는 값을 도출할 수 있다.
이 글의 문제는 인프런 강의에서 참고하였습니다.
'프로그래밍 > 알고리즘' 카테고리의 다른 글
[알고리즘 - 프로그래머스, 인프런] 2019 카카오 겨울 개발자 인턴십 코딩테스트 문제 - 크레인 인형뽑기(카카오) (1) | 2024.02.06 |
---|---|
[알고리즘 - 인프런] 올바른 괄호 (stack 기본 문제) (0) | 2024.02.06 |
[ArrayList를 Array로 형 변환] - 코딩테스트 출력값이 안 맞을 때 (0) | 2024.02.03 |
[for each 문] - 알고리즘 공부하다 알게 된 신기한 것 (0) | 2024.02.01 |
[알고리즘 - 인프런] 두 배열 합치기 (two pointer 단순 구현, sort 활용) (0) | 2024.02.01 |