작성
·
213
·
수정됨
0
package slidingwindow;
import java.util.Scanner;
public class MaximumSales {
static int solution(int n, int k, int[] arr) {
int p1 = 1;
int sum = 0;
int max = 0;
for(int i = 0; i < k; i++) {
sum += arr[i];
}
// 최초 값을 max에 대입
max = sum;
// 최초 p[0] + p[1] + p[2] .... 값 제외
// p[1] + p[2] ... 부터
while(p1 < n-k+1) {
sum = sum - arr[p1-1] + arr[p1+k-1] ;
p1++;
max = max > sum ? max : sum;
}
return max;
}
public static void main(String[] args) {
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(MaximumSales.solution(n, k, arr));
}
}
답변 1
0
안녕하세요, 인프런 AI 인턴입니다.
제시하신 자바 코드의 시간복잡도에 대해 설명드리겠습니다.
먼저 코드의 로직을 보면 처음 k개 요소의 합을 구하고 이를 초기 최대값으로 설정합니다. 그 후 슬라이딩 윈도우 기법인 누적 합을 이용해 배열을 한 칸씩 옮겨가며 최대값을 갱신합니다. 이 과정에서 요소의 추가와 제거가 상수 시간에 이뤄지기 때문에 n-k번의 반복으로 각 요소가 한 번씩만 처리됩니다.
시간복잡도는 구간 합을 구하는 초기 과정에서 O(k), 이후 슬라이딩 윈도우를 적용하는 데 O(n-k)가 소요됩니다. 따라서 전체적인 시간복잡도는 O(k + (n-k))이 되고, 이는 O(n)으로 표현할 수 있습니다.
최대 매출 문제의 경우 슬라이딩 윈도우 알고리즘을 적절하게 사용한다면 동일하게 O(n)의 시간복잡도로 문제를 해결할 수 있습니다. 따라서 제공하신 코드는 최대 매출 문제의 효율적인 해결 방안 중 하나로 볼 수 있으며, 동일한 시간복잡도가 나올 것입니다.
답변이 도움이 되셨길 바라며, 추가적인 질문이 있으시면 언제든 문의해주시길 바랍니다.