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

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) 알고리즘 문제풀이 : 코딩테스트 대비 - 인프런 | 강의

 

문제 3 :

n일 동안의 매출기록을 주고 연속된 k일 동안 최대 매출액이 얼마인지 구하는 프로그램을 작성하시오.

첫번째 줄에 n(5<=n<=100,000)과 k(2<=k<=n)가 주어지고

두번째 줄에 n개의 숫자열이 주어진다.

입력예제

10 3

12 15 11 20 25 10 20 19 13 15

출력예제

56

 

소스코드 :

import java.util.*;
class Main {
	public int solution(int n, int k, int[] arr) {
		int answer = 0, sum = 0;
		for(int i=0; i<k; i++) {
			sum += arr[i];
		}
		answer = sum;
		for(int i=k; i<n; i++) {
			sum += (arr[i] - arr[i-k]);
			answer = Math.max(answer, sum);
		}
		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));
	}
}

 

풀이 :

슬라이딩 윈도우 알고리즘을 적용하였다.

일반적으로 생각하기에 2중 for문으로 풀 수 있는데, 슬라이딩 윈도우 알고리즘을 사용하면

시간복잡도가 줄어든다.

먼저 연속된 k일 동안의 합을 answer에 넣어두고,

그 이후 숫자부터 for문을 돌리면서 뒤에 나올 숫자를 하나 더하고 앞에 나왔던 숫자를 하나 빼는 것을 반복하며

answer 값과 크기를 비교해 클 경우 answer에 해당 값을 저장한다.

최종적으로는 answer값은 k일 간의 최대 매출액이 저장된다.

 

 

 

문제4 :

n개의 수로 이루어진 수열이 주어진다.

이 수열에서 연속부분수열 합이 특정숫자 k가 되는 경우가 몇 번 있는지 구하는 프로그램을 작성하여라

입력예제

8 6

1 2 1 3 1 1 1 2

출력예제

3

(합이 6이 되는 연속부분 수열이 {2,1,3}, {1,3,1,1}, {3,1,1,1} 으로 총 3개이다.)

 

소스코드 :

import java.util.*;
class Main {
	public int solution(int n, int k, int[] arr) {
		int answer = 0, lt = 0, sum = 0;
		for (int rt=0; rt<n; rt++) {
			sum += arr[rt];
			while (sum > k) {
				sum -= arr[lt++];
			}
			if (sum == k) answer++;
		}
		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));
	}
}

 

풀이 :

이 문제 역시 이중 for문으로 O(n²)의 시간복잡도를 잡아먹는 대신

알고리즘을 사용해 O(n)으로 문제를 해결한다.

투포인터 알고리즘 + 슬라이딩 윈도우 알고리즘을 적용하여 문제를 해결하였다.

lt와 rt를 두고 rt값을 인덱스로 두는 for문을 돌린다.

sum > k일 경우 sum에 arr[lt]값을 빼고 lt값을 1 증가시킨다.

sum == k일 경우 answer++;

 

해당 while문은 lt가 0부터 n까지 증가하는 동안만 반복해 총 n번 반복한다.

즉, for문 안의 while문은 lt가 n까지 가면 멈춰 총 반복횟수가 n번이다.

따라서 O(n)의 시간복잡도를 가진다.