3. 최대 매출

1. 문제

N일 동안의 매출 기록을 가지고 K일 동안의 최대 매출액이 얼마인지 구하시오

만약 12 15 11 20 25 10 20 19 13 15 가 있다면 11 20 25 로서의 3일간의 매출이 가장 높다.

 

2 - 2. 나의 풀이

첫번째 풀이 시도

1. k일 간의 매출을 구하는 메서드 (for문 사용)

2. 0 ~ n - k -1일 만큼의 k일 뒤 매출을 최댓값을 갱신하기 (for 문 사용)

 

2중 for문의 사용으로 시간 복잡도가 N^2 로서 시간 초과가 나서 오답처리 됐다.

 

두번째 풀이 시도 (Sliding Window에서 힌트를 얻음)

위 예시로 설명하자면

1. 12 15 11 같이 k 일간의 최대 매출액을 구한다.

2. 다음날 매출 값을 더하고 가장 빠른 날의 매출 값을 뺀다.

for(int i = k, i < n-1 ; i++){
	answer = answer + arr[i] - arr[i-k];
    //max에는 for문 전에 첫번째 k일 동안의 매출기록을 저장해둔다.
	if(max > answer) max = answer; 
}

 

3 - 1. 강의 풀이

나와 풀이가 같아서 설명은 생략한다.

최댓값을 갱신하는 과정에서 Math.max 메서드를 사용했다는 차이가 있다.

 

for(int i = k, i < n-1 ; i++){
	answer = answer + arr[i] - arr[i-k];
    //max에는 for문 전에 첫번째 k일 동안의 매출기록을 저장해둔다.
	max = Math.max(answer, max);
}

 

 

4. 얻어갈 점

시간 복잡도를 생각하면서 알고리즘을 짜는게 추후에도 좋다.