inflearn logo
강의

강의

N
챌린지

챌린지

멘토링

멘토링

N
클립

클립

로드맵

로드맵

지식공유

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

3. 최대 매출(Sliding window)

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

283

이주용

작성한 질문수 14

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));

	}

}

java 코딩-테스트

답변 1

0

인프런 AI 인턴

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

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

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

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

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

안녕하세요. 바뀐 채점사이트 관련해서 문의드립니다.

0

28

1

갑자기 채점 사이트가 바뀌었어요

0

32

1

문제 리스트 페이지

0

29

1

채점 사이트 관련 질문드립니다

0

23

1

봉우리 문제 질문입니다

0

81

2

씨름 선수 문제에서 각 선수의 몸무게나 키가 같을 수도 있다면?

0

64

0

이 코드랑 영상 코드중에 뭐가 더 좋은 코드인가요?

0

72

0

가중치 방향 그래프에서 가중치가 0인 간선을 표현하는 방법

0

67

1

좌표 정렬 문제 이 코드가 왜 틀린지 모르겠습니다 ㅠㅠ

0

85

2

6-7 강의에서

0

48

1

6-6. 장난꾸러기 질문 있습니다.

0

45

1

강의 수강후 코딩테스트

0

110

1

answer 변수 사용 여부

0

44

1

2중 for문

1

85

2

2-11. 임시반장정하기 (Runtime Error)

0

63

1

혹시 LinkedList 같은 자료 구조들은 따로 배우지 않나요?

0

70

1

이런 풀이는 어떨까요

0

43

1

자바 스트림 방식의 효율성 질문 드립니다.

0

57

1

알고리즘 자료 구조들..

0

62

1

StringBuilder vs BufferdWriter

0

48

1

원더랜드(프림)

0

50

1

이런 코드는 어떤가요?

0

61

1

bfs 풀이

0

57

1

병합정렬

0

56

1