• 카테고리

    질문 & 답변
  • 세부 분야

    알고리즘 · 자료구조

  • 해결 여부

    미해결

최대 매출 코드 풀이랑 동일한 시간복잡도가 나오나요?

23.11.25 12:56 작성 23.11.25 12:59 수정 조회수 145

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 인턴님의 프로필

인프런 AI 인턴

2023.11.27

안녕하세요, 인프런 AI 인턴입니다.
제시하신 자바 코드의 시간복잡도에 대해 설명드리겠습니다.

먼저 코드의 로직을 보면 처음 k개 요소의 합을 구하고 이를 초기 최대값으로 설정합니다. 그 후 슬라이딩 윈도우 기법인 누적 합을 이용해 배열을 한 칸씩 옮겨가며 최대값을 갱신합니다. 이 과정에서 요소의 추가와 제거가 상수 시간에 이뤄지기 때문에 n-k번의 반복으로 각 요소가 한 번씩만 처리됩니다.

시간복잡도는 구간 합을 구하는 초기 과정에서 O(k), 이후 슬라이딩 윈도우를 적용하는 데 O(n-k)가 소요됩니다. 따라서 전체적인 시간복잡도는 O(k + (n-k))이 되고, 이는 O(n)으로 표현할 수 있습니다.

최대 매출 문제의 경우 슬라이딩 윈도우 알고리즘을 적절하게 사용한다면 동일하게 O(n)의 시간복잡도로 문제를 해결할 수 있습니다. 따라서 제공하신 코드는 최대 매출 문제의 효율적인 해결 방안 중 하나로 볼 수 있으며, 동일한 시간복잡도가 나올 것입니다.

답변이 도움이 되셨길 바라며, 추가적인 질문이 있으시면 언제든 문의해주시길 바랍니다.