Java 투포인터, 슬라이딩 윈도우 알고리즘3

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

자바(Java) 알고리즘 문제풀이 : 코딩테스트 대비 - 인프런 | 강의

 

문제5 :

양의 정수 n(7<=n<=1000)이 입력되면 2개 이상의 연속된 자연수 합으로 정수 n을 표현하는 방법의 가짓수를

출력하는 프로그램을 작성하시오.

예를 들어 n = 15일 경우,

7 + 8 , 4 + 5 + 6 , 1 + 2 + 3 + 4 + 5 로 답은 3이다.

입력예제

15

출력예제

3

 

소스코드 :

import java.util.*;
class Main {
	public int solution(int n) {
		int answer = 0;
		// 배열 생성
		int s = n / 2 + 1;
		int[] arr = new int[s];
		for(int i=0; i<s; i++) {
			arr[i] = i + 1;
		}
		// 합이 n이 되는 연속부분수열 구하기
		int lt=0, sum=0;
		for(int rt=0; rt<s; rt++) {
			sum += arr[rt];
			while (sum > n) {
				sum -= arr[lt++];
			}
			if (sum == n) answer++;
		}
		return answer;
	}

	public static void main(String[] args) {
		Main T = new Main();
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		System.out.println(T.solution(n));
	}
}

 

풀이 :

양의 정수 n이 주어지면 n/2+1 보다 큰 수가 연속된 수의 합으로 나올 수 없으므로

1부터 n/2+1까지만 배열을 생성한다.

생성한 해당 배열에서 투포인터와 슬라이딩 윈도우 알고리즘을 적용해 원하는 정답을 알아냈다.

 

 

문제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

 

소스코드 :

import java.util.*;
class Main {
	public int solution(int n, int k, int[] arr) {
		int answer = 0, cnt = 0, lt = 0;
		for(int rt=0; rt<n; rt++) {
			if (arr[rt] == 0) cnt++;
			while (cnt > k) {
				if (arr[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[] arr = new int[n];
		for(int i=0; i<n; i++) {
			arr[i] = sc.nextInt();
		}
		System.out.println(T.solution(n, k, arr));
	}
}

 

풀이 :

투포인터 + 슬라이딩 알고리즘을 적용한다.

lt와 rt를 두고 왼쪽에서부터 이동하며 문제를 해결한다.

수열에서 최대 k번을 0에서 1로 바꿀 수 있으므로

cnt가 k보다 커질 경우 lt를 이동시킨다.