본문 바로가기
Java/Java 알고리즘 인프런

[Ch.03 - 투 포인터] 3. 최대 매출 (+ 슬라이딩 윈도우)

앤 썸 2022. 5. 9. 14:46
반응형

3.최대 매출
N일 동안 매출기록 중 연속 k일 동안 최대 매출액 구하기

 

입력값

10 3

12 15 11 20 25 10 20 19 13 15

 

출력값

56

 

package twopointer.ch03;

import java.util.Scanner;

//최대 매출
//총 n일 중, 연속 k일간의 최대 매출
class Twopointer03_1 {

	public int solution(int n, int k, int[] arr) {
		int sum = 0;
		int tmp = 0;
		int p1 = 0;
		int p2 = 1;

		while (p1 < n) {
			tmp = 0;
			p2 = p1 + 1;
			tmp = arr[p1];
			while (p2 - p1 < k &&p2 < n) {
				tmp += arr[p2++];
				if (p2 - p1 == 3 && tmp > sum) {
					sum = tmp;
				}
			}
			p1++;
		}
		return sum;
	}

	public static void main(String[] args) {
		Twopointer03_1 T = new Twopointer03_1();
		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(n, k, arr));
		

	}

}

-> Timeout 발생

 

 

 

 

1.n일 중 -> int [n]

2. 연속 k일 최대 매출액 -> 최대 값 sum, k일까지의 합계 tmp와 이전 sum값 크기 비교

3. while (p1 < n)

p1이 n보다 작으면 계속 반복하면서, p2를 p1+1로 지정하고, 합계에 미리 arr[p1]값을 넣어둔다.

4. while (p2 - p1 < k &&p2 < n) 

p2와 p1의 차가 k보다 작고, p2가 n보다 작으면 계속 반복하면서, tmp에 arr[p2]값을 더한다.

5. if (p2 - p1 == 3 && tmp > sum) 

p2-p1이 3이고, 해당하는 3일간의 합계가 이전 합계보다 크면, 해당하는 3일간의 합계를 sum으로 지정한다.

package twopointer.ch03;

import java.util.Scanner;

//최대 매출
//총 n일 중, 연속 k일간의 최대 매출
class Twopointer03_1 {

	public int solution(int n, int k, int[] arr) {
		int sum = 0;
		int tmp = 0;
		int p1 = 0;
		int p2 = 1;

		while (p1 < n) {
			tmp = 0;
			p2 = p1 + 1;
			tmp = arr[p1];
			while (p2 - p1 < k &&p2 < n) {
				tmp += arr[p2++];
				if (p2 - p1 == 3 && tmp > sum) {
					sum = tmp;
				}
			}
			p1++;
		}
		return sum;
	}

	public static void main(String[] args) {
		Twopointer03_1 T = new Twopointer03_1();
		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(n, k, arr));
		

	}

}

-> Timeout 발생

-> while 문 사용하지 않고 풀이해, 시간 단축 방법 모색

 

//최대 매출

//슬라이딩 윈도우
//이중 for문을 이용하지 않고, while문을 이용해 복잡도를 낮춘다.
//for문 -> n x k
//while문 -> n

//ds
//n일 중 -> int[]
//연속 K일 최대 매출액 -> sum, k까지 sum, tmp

import java.util.Scanner;

public class Main {
	public int solution(int[] arr, int k) {
		int answer = Integer.MIN_VALUE;

		for(int i=0;i<arr.length-k;i++) {
			int tmp = 0;
			for (int j = i; j < i + k; j++) {
				tmp += arr[j];
			}
			answer = Math.max(tmp, answer);
		}

		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.print(T.solution(arr, k));
	}

}

-> while문을 이중for문으로 바꿔도 Timeout 발생

 

: 이중for문을 사용하지않고 for문 한번을 사용해, 구현

먼저, 0부터 k까지 구한 후 -> tmp+arr[i]-arr[i-k] 반복

//최대 매출

//슬라이딩 윈도우
//이중 for문을 이용하지 않고, while문을 이용해 복잡도를 낮춘다.
//for문 -> n x k
//while문 -> n

//ds
//n일 중 -> int[]
//연속 K일 최대 매출액 -> sum, k까지 sum, tmp

import java.util.Scanner;

public class Main {
	public int solution(int[] arr, int k) {
		int answer = Integer.MIN_VALUE;
		int tmp = 0;
		
		for(int i=0;i<k;i++) {
			
			tmp += arr[i];
			answer = tmp;
		}
		for(int i=k;i<arr.length;i++) {
			tmp=tmp+arr[i]-arr[i-k];
			answer=Math.max(answer, tmp);
		}

		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.print(T.solution(arr, k));
	}

}

 

import java.util.Scanner;
  
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();
    }
    System.out.println(solution(n,m, arr));
  }
  static int solution(int n, int m, int[] arr){
    //슬라이딩 윈도우
    int sum=0;
    int tmp=0;
    for(int i=0;i<n-m+1;i++){
      sum=0;
      for(int j=i;j<i+m;j++){
        sum+=arr[j];
      }
      tmp=Math.max(tmp,sum);
    }
    return tmp;
  }
}

-->TimeLimit

 

+) 세련된 풀이

1. for(int i=0;i<k;i++)

처음 0일부터 k일 동안(0일 1일 2일... k-1일 총 k일) 매출액을 더해서 sum에 넣는다.

answer에 해당 합계를 저장

2. for(int i=k;i<n;i++)

k일부터 n일까지 반복하는데, 최댓값을 구하기 위해 k일마다 맨 앞일자를 빼고 다음 날짜를 넣는다.

-> sum+=(arr[i]-arr[i-k])

즉, k일 매출에서 k+1일 매출을 뺀 값, k일 매출에서 k+2일 매출을 뺀 값 ... k일 매출에서 n-k일 매출을 뺀 값을

차례대로 비교해 가장 큰값을 answer로 설정

 

: 처음 k일까지의 매출을 구하고, 다음날부터 k+1일까지 구해서 비교, 다다음날부터 k+2일까지 구해서 비교 [K일 합계]

-> Math.max()로 값 비교해 큰 값을 answer로 지정 


import java.util.Scanner;

public class Main {
	//최대 매출
	//N일 동안 매출기록 중 연속 k일 동안 최대 매출액 구하기
	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(n,k,arr));
	}
	public int solution(int n, int k, int[] arr) {
		//1.ds
		int answer, sum=0;
		
		//2.for,while
		for(int i=0;i<k;i++) {
			//연속 k일동안 최대
			sum+=arr[i];
		}	
			answer=sum;
			//K일동안 합계 -> 결과로 저장
		
		//k일부터 시작
		for(int i=k;i<n;i++) {
			sum+=(arr[i]-arr[i-k]);
			//k일 부터 n까지 반복 -> 최댓값을 구하기위해, k일부터 n일까지
			//k=3일경우, (arr[3]-arr[0])+(arr[4]-arr[1])+(arr[5]-arr[2])
			//4일-1일+5일-2일+6일-3일
			//1일+2일+3일 + 4일-1일 +5일-2일 ... -> 3일마다 계산
			//즉, 3일마다, 맨 앞일자를 빼고 다음 날짜를 넣는다.
			
			answer=Math.max(answer, sum);
			
		}
		return answer;
	}
	

}

 

 

1. 초기값 설정 [m일간 매출]

2. 하루 추가, 첫날 빼기

import java.util.Scanner;
  
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();
    }
    System.out.println(solution(n,m, arr));
  }
  static int solution(int n, int m, int[] arr){
    //슬라이딩 윈도우
    //초기값 설정
    int sum=0;
    int tmp=0;
    for(int i=0;i<m;i++){
      sum+=arr[i];
    }
    tmp=sum;
    int cnt=0;
    for(int j=m;j<n;j++){
      sum+=arr[j];
      sum-=arr[cnt++];
      tmp=Math.max(tmp,sum);
    }
    
    return tmp;
  }
}
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;
    
    for(int i=0; i<k; i++){
      answer+=arr[i];  
    }
    int result=answer;
    for(int i=1; i<n-k+1; i++){
      answer-=arr[i-1];
      answer+=arr[i+k-1];
      result=Math.max(result,answer);
    }
    System.out.println(result);
  }
}

 

 

+) 03.02

import java.util.Scanner;
  
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 m){
   int answer=0;
   for(int i=0;i<m;i++){
     answer+=arr[i];
   }
   
   int result=answer;
   for(int i=m;i<arr.length;i++){
     result-=arr[i-m];
     result+=arr[i];
     answer=Math.max(result, answer);
   }
   return answer;
 }
}
반응형
저작자표시 비영리

'Java > Java 알고리즘 인프런' 카테고리의 다른 글

[Ch.01 - String] 01. 문자 찾기 (+ toCharArray)  (0) 2022.05.12
[Ch.03 - 투 포인터] 6. 최대 길이 연속부분수열 ###  (0) 2022.05.09
[Ch.03 - 투 포인터] 5. 연속된 자연수의 합 # (+ for-while)  (0) 2022.05.09
[Ch.03 - 투 포인터] 4. 연속 부분수열 ##  (0) 2022.05.09
[Ch.03 - 투 포인터] 2. 공통원소 구하기 (+하나씩 확인하는 방법)  (0) 2022.05.09

'Java/Java 알고리즘 인프런' Related Articles

티스토리툴바