인프런 커뮤니티 질문&답변

이주용님의 프로필 이미지
이주용

작성한 질문수

자바(Java) 알고리즘 문제풀이 입문: 코딩테스트 대비

3. 최대 매출(Sliding window)

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

작성

·

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)의 시간복잡도로 문제를 해결할 수 있습니다. 따라서 제공하신 코드는 최대 매출 문제의 효율적인 해결 방안 중 하나로 볼 수 있으며, 동일한 시간복잡도가 나올 것입니다.

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

이주용님의 프로필 이미지
이주용

작성한 질문수

질문하기