6. 최대 길이 연속 부분수열
0과 1로 구성된 길이가 N인 수열에서, 최대 k번 변경가능한데, 0을 1로 변경가능
최대 k번의 변경을 통해 1로만 구성된 최대 길이의 연속부분수열 출력
입력값
14, 2
1 1 0 0 1 1 0 1 1 0 1 1 0 1
출력값
8
1. answer와 sum -> 구간별 연속부분수열 개수를 sum에 저장해 answer와 비교
2. 포인터 1 p1, 포인터2 p2, p2의 개수 p2_n
3. 1로 바꾼 마지막 위치 zero, 현재 세고 있는 위치 count
4. arr2는 arr배열을 복사한 배열로, 매번 리셋
5. while (p2 < n && p2_n < k)
if (arr[p2] == 0)
0인 값 1로 바꾸고
if(p2_n==1)
처음 1로 바꾼 위치 기억
else
0이 아니므로 p2 증가
6. for (int i = count; i < n; i++)
if (arr[i] == 1)
1인 값이 존재하면 sum +1하고,
if (answer < sum)
결과값보다 sum이 크면 sum을 결과값에 대입
else
배열값이 1아니면 아니면 멈춤
6. 현재 세고 있는 위치와 1로 바꾼 마지막 위치 설정후 다시 반복
package twopointer.ch03;
//최대 길이 연속부분수열
//0과 1로 구성된 길이가 n인 수열
//최대 k번 0을 1로 변경해 최대 길이의 연속부분수열을 찾아라
//1 1 0 0 1 1 0 1 1 0 1 1 0 1
import java.util.Scanner;
class Twopointer06_1 {
static int[] arr;
public int solution(int n, int k) {
int answer = 0;
int sum = 0;
int p1 = 0;
int p2 = 0;
int p2_n = 0;
int zero=0;
int count=0;
// p2의 개수 세기
int [] arr2= arr.clone();
while (p1 < n-1) {
arr=arr2.clone();
while (p2 < n && p2_n < k) {
if (arr[p2] == 0) {
arr[p2] = 1;
p2++;
p2_n++;
if(p2_n==1) {
zero=p2;
}
}
else {
p2++;
}
}
for (int i = count; i < n; i++) {
if (arr[i] == 1) {
sum++;
if (answer < sum) {
answer = sum;
}
} else {
break;
}
}
p2_n = 0;
p1++;
p1=zero;
p2=zero;
count=zero;
sum = 0;
}
return answer;
}
public static void main(String[] args) {
Twopointer06_1 T = new Twopointer06_1();
Scanner kb = new Scanner(System.in);
int n = kb.nextInt();
int k = kb.nextInt();
arr = new int[n];
for (int i = 0; i < n; i++) {
arr[i] = kb.nextInt();
}
System.out.println(T.solution(n, k));
}
}
import java.util.Scanner;
public class Main {
public int solution(int[] arr , int k) {
int answer=0, tmp=0, lt=0, k2=k;
for(int rt=0;rt<arr.length;rt++) {
if(arr[rt]==1) {
tmp++;
answer=Math.max(tmp, answer);
}else if(arr[rt]==0 && k!=0) {
k--;
tmp++;
answer=Math.max(tmp, answer);
}else if(k==0) {
tmp=0;
lt++;
rt=lt;
k=k2;
}
}
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(arr,k));
}
}
+) 세련된 풀이
1. int answer=0, cnt=0, lt=0;
결과값, 카운트, 포인터 변수 정의
2. for(int rt=0;rt<n;rt++) {
포인터2는 n까지 반복하는데,
if(arr[rt]==0)
포인터2의 값이 0일경우 카운트를 증가시킨다.
while(cnt>m) {
변경가능한수 m보다 카운트가 크면 반복
if(arr[lt]==0)
포인터1의 값이 0이면 카운트에서 빼고, 포인터1의 값을 증가시킨다.
3. answer=Math.max(answer, rt-lt+1);
포인터2에서 포인터1을 빼고 +1한 값과 결과값을 비교해서 큰 값이 큰값
즉, 결과값은 0이고, rt-lt+1은, 포인터2의 값이 0인곳이 존재하면 cnt를 증가시키므로,
변경가능하다면, 포인터1의 값이 0이면 바꾸고, 카운트를 감소시킨다.
package twopointer.ch03;
import java.util.Scanner;
public class Twopointer06 {
//# 최대 길이 연속 부분수열
//0과 1로 구성된 길이가 N인 수열에서, 최대 k번 변경가능한데, 0을 1로 변경가능
//최대 k번의 변경을 통해 1로만 구성된 최대 길이의 연속부분수열을 찾아라.
public static void main(String[] args) {
Twopointer06 T = new Twopointer06();
Scanner kb = new Scanner(System.in);
int n=kb.nextInt();
int m=kb.nextInt();
int[] arr=new int[n];
for(int i=0;i<n;i++) {
arr[i]=kb.nextInt();
}
System.out.println(T.solution(n,m,arr));
kb.close();
}
public int solution(int n,int m,int[]arr) {
//1.ds
int answer=0, cnt=0, lt=0;
//결과값, 카운트, 포인터 변수 정의
//2.for, while
for(int rt=0;rt<n;rt++) {
//포인터2는 n까지 반복하는데,
if(arr[rt]==0)
cnt++;
//포인터2의 값이 0일경우 카운트를 증가시킨다.
while(cnt>m) {
//변경가능한수 m보다 카운트가 크면 반복
if(arr[lt]==0)
cnt--;
//포인터1의 값이 0이면 카운트에서 뺸다.
lt++;
//포인터1의 값을 증가시킨다.
}
answer=Math.max(answer, rt-lt+1);
//포인터2에서 포인터1을 빼고 +1한 값과 결과값을 비교해서 큰 값이 큰값
//결과값은 0이고, rt-lt+1은, 포인터2의 값이 0인곳이 존재하면 cnt를 증가시키므로, 변경가능하다면, 포인터1의 값이 0이면 바꾸고, 카운트를 감소시킨다.
}
return answer;
}
}1. 0-> 1로 바꿀 수 있는 K값을 줄이면서, 0보다 작아지면 while문 반복
2. 0일 때 cnt값을 늘리면서, k보다 커지면 while문 반복하면서 줄인다.
1. 0-> 1로 바꿀 수 있는 K값을 줄이면서, 0보다 작아지면 while문 반복
import java.util.Scanner;
public class Main {
public static void main(String[] args){
Scanner in=new Scanner(System.in);
int n = in.nextInt();
int k = in.nextInt();
int[] arr = new int[n];
for(int i=0;i<n;i++){
arr[i]=in.nextInt();
}
int answer=0;
int result=Integer.MIN_VALUE;
//k번 0->1로 변경가능
int lt=0;
int tmp=0;
for(int rt=0;rt<n;rt++){
if(arr[rt]==0) k--;
while(k<0){
if(arr[lt]==0) k++;
lt++;
}
result=Math.max(rt-lt+1,result);
}
System.out.println(result);
}
}
2. 0일 때 cnt값을 늘리면서, k보다 커지면 while문 반복하면서 줄인다.
import java.util.Scanner;
public class Main {
public static void main(String[] args){
Scanner in=new Scanner(System.in);
int n = in.nextInt();
int k = in.nextInt();
int[] arr = new int[n];
for(int i=0;i<n;i++){
arr[i]=in.nextInt();
}
int answer=0;
int result=Integer.MIN_VALUE;
//k번 0->1로 변경가능
int lt=0;
int cnt=0;
for(int rt=0;rt<n;rt++) {
//포인터2는 n까지 반복하는데,
if(arr[rt]==0)
cnt++;
//포인터2의 값이 0일경우 카운트를 증가시킨다.
while(cnt>k) {
//변경가능한수 k보다 카운트가 크면 반복
if(arr[lt]==0)
cnt--;
//포인터1의 값이 0이면 카운트에서 뺸다.
lt++;
//포인터1의 값을 증가시킨다.
}
answer=Math.max(answer, rt-lt+1);
//포인터2에서 포인터1을 빼고 +1한 값과 결과값을 비교해서 큰 값이 큰값
//결과값은 0이고, rt-lt+1은, 포인터2의 값이 0인곳이 존재하면 cnt를 증가시키므로, 변경가능하다면, 포인터1의 값이 0이면 바꾸고, 카운트를 감소시킨다.
}
System.out.println(answer);
}
}
+)03.02
import java.util.Scanner;
import java.util.*;
public class Main {
public static void main(String[] args){
Scanner in=new Scanner(System.in);
int n = in.nextInt();
int m = in.nextInt();
int[] arr = new int[n];
for(int i=0;i<n;i++){
arr[i]=in.nextInt();
}
Main main =new Main();
System.out.println(main.solution(arr,m));
}
public int solution(int[] arr, int k){
int lt=0;
int cnt=0;
int result=0;
for(int i=0;i<arr.length;i++){
if(arr[i]==0) {
cnt++;
}
while(cnt>k){
if(arr[lt]==0) cnt--;
lt++;
}
result=Math.max(result, i-lt+1);
}
return result;
}
}'Java > Java 알고리즘 인프런' 카테고리의 다른 글
| [Ch.01 - String] 02. 대소문자 변환 (+ toCharArray) (0) | 2022.05.12 |
|---|---|
| [Ch.01 - String] 01. 문자 찾기 (+ toCharArray) (0) | 2022.05.12 |
| [Ch.03 - 투 포인터] 5. 연속된 자연수의 합 # (+ for-while) (0) | 2022.05.09 |
| [Ch.03 - 투 포인터] 4. 연속 부분수열 ## (0) | 2022.05.09 |
| [Ch.03 - 투 포인터] 3. 최대 매출 (+ 슬라이딩 윈도우) (0) | 2022.05.09 |