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 |