최대 매출
설명
현수의 아빠는 제과점을 운영합니다. 현수 아빠는 현수에게 N일 동안의 매출기록을 주고 연속된 K일 동안의 최대 매출액이 얼마인지 구하라고 했습니다.
만약 N=10이고 10일 간의 매출기록이 아래와 같습니다. 이때 K=3이면
12 1511 20 2510 20 19 13 15
연속된 3일간의 최대 매출액은 11+20+25=56만원입니다.
여러분이 현수를 도와주세요.
코드
public class MaximumSale {
public static void main(String[] args){
Scanner in=new Scanner(System.in);
int input1 = in.nextInt();
int input2 = in.nextInt();
int[] arr = new int[input1];
for(int i=0; i<input1; i++){
arr[i] = in.nextInt();
}
int solution = solution2(input2, arr);
System.out.println(solution);
}
//실패
public static int solution(int input, int[] arr){
int answer = 0;
ArrayList<Integer> list = new ArrayList<>();
for(int i : arr){
list.add(i);
}
list.add(-1);
int p = 0;
logic : while(true){
int sum = 0;
for(int i=p; i<input+p; i++){
int su = list.get(i);
if(su == -1) break logic;
sum += su;
}
answer = Math.max(answer, sum);
p++;
}
return answer;
}
//sliding window algorithm
public static int solution2(int n, int[] arr){
int answer = 0;
int sum = 0;
//n까지 먼저 값을 구하고
for(int i=0; i<n; i++){
answer += arr[i];
}
sum = answer;
//다음 값부터는 sliding window 알고리즘으로 구현
for(int i=n; i<arr.length; i++){
sum = sum - arr[i-n] + arr[i];
answer = Math.max(answer, sum);
}
return answer;
}
}
public class MaximumSale {
public static void main(String[] args){
Scanner in=new Scanner(System.in);
int input1 = in.nextInt();
int input2 = in.nextInt();
int[] arr = new int[input1];
for(int i=0; i<input1; i++){
arr[i] = in.nextInt();
}
int solution = solution2(input2, arr);
System.out.println(solution);
}
//실패
public static int solution(int input, int[] arr){
int answer = 0;
ArrayList<Integer> list = new ArrayList<>();
for(int i : arr){
list.add(i);
}
list.add(-1);
int p = 0;
logic : while(true){
int sum = 0;
for(int i=p; i<input+p; i++){
int su = list.get(i);
if(su == -1) break logic;
sum += su;
}
answer = Math.max(answer, sum);
p++;
}
return answer;
}
//sliding window algorithm
public static int solution2(int n, int[] arr){
int answer = 0;
int sum = 0;
//n까지 먼저 값을 구하고
for(int i=0; i<n; i++){
answer += arr[i];
}
sum = answer;
//다음 값부터는 sliding window 알고리즘으로 구현
for(int i=n; i<arr.length; i++){
sum = sum - arr[i-n] + arr[i];
answer = Math.max(answer, sum);
}
return answer;
}
}
문제를 보고 가장 먼저 solution으로 문제를 풀었다. 답은 나왔지만 문제는 시간복잡도였다. 문제 자체가 O(N)으로 풀어야하는 문제였는데 O(N^2)으로 풀이를 했으니 당연히 time out이 나버려서 실패했다.
그 후 강의를 들으며 sliding window algorithm에 대해 학습하였고 solution2로 문제를 풀게 되었다. 배열 내에서 범위를 비교할 때 이중 for문을 돌릴 필요 없이 빠르게 풀어낼 수 있는 방법이다.
sliding window에 대한 설명을 추가하는 것이 이 글에 더 좋은 방향성일듯!
Author And Source
이 문제에 관하여(최대 매출), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@ililil9482/최대-매출저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)