티스토리 뷰
반응형
문제
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로 구성된 수열이 주어집니다.
출력
첫 줄에 최대 길이를 출력하세요.
예시 입력
14 2
1 1 0 0 1 1 0 1 1 0 1 1 0 1
예시 출력
8
문제 풀이
[첫번째 풀이]
import java.util.*;
public class Main {
public int solution(int n, int k, int[] numbers) {
int count = 0, start = 0, max = 0;
ArrayList<Integer> zero = new ArrayList<>();
for (int i=0; i<n; i++) {
count++;
if (numbers[i] == 0) {
zero.add(i + 1);
if (k > 0) k--;
else {
int tmp = zero.get(start);
if (start > 0) tmp -= zero.get(start - 1);
count -= tmp;
start++;
}
}
max = Math.max(max, count);
}
return max;
}
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt();
int k = scanner.nextInt();
int[] numbers = new int[n];
for (int i=0; i<n; i++) {
numbers[i] = scanner.nextInt();
}
Main main = new Main();
System.out.println(main.solution(n, k, numbers));
}
}
(Time 796ms / Memory 35MB)
- 0의 위치값을 담는 배열리스트를 만들어 이용했다.
반응형
'Java > Coding Test' 카테고리의 다른 글
[코딩테스트] 연속된 자연수의 합 (0) | 2022.03.21 |
---|---|
[코딩테스트] 연속 부분수열 (0) | 2022.03.21 |
[코딩테스트] 최대 매출 (0) | 2022.03.17 |
[코딩테스트] 공통원소 구하기 (0) | 2022.03.14 |
[코딩테스트] 두 배열 합치기 (0) | 2022.03.13 |