[COS Pro 1급 Python] 3차 기출문제 9) 팝업 스토어를 열 최적의 날짜

정은·2023년 8월 12일

COS Pro 1급

목록 보기

24/26

문제 9)

모 매장에서는 팝업스토어를 열려고 합니다. 팝업스토어란 한정 기간 문을 여는 매장입니다. 팝업스토어는 k일 동안 연속해서 열 예정입니다. n일 동안의 추정 매출액이 주어질 때, 언제 팝업스토어를 열어야 가장 매출이 높을지 알아보려 합니다.

n일 간의 추정 매출액이 담긴 리스트 revenue와 팝업스토어를 열 날의 수 k가 매개변수로 주어질 때, 최대 매출액 합을 return 하도록 solution 함수를 작성했습니다. 그러나, 코드 일부분이 잘못되어있기 때문에, 몇몇 입력에 대해서는 올바르게 동작하지 않습니다. 주어진 코드에서 한 줄만 변경해서 모든 입력에 대해 올바르게 동작하도록 수정하세요.

매개변수 설명

추정 매출액이 담긴 리스트 revenue와 팝업스토어를 열 날의 수 k가 solution 함수의 매개변수로 주어집니다.

revenue의 길이는 1 이상 200,000 이하입니다.
revenue의 원소는 10,000 이하의 자연수입니다.
k는 1 이상 100,000 이하이고, revenue의 길이보다 작거나 같습니다.

return 값 설명

최대 매출액 합을 return 해주세요.

예시

revenue	k	return
[1, 1, 9, 3, 7, 6, 5, 10]	4	28
[1, 1, 5, 1, 1]	1	5

예시 설명

예시 #1
4일간 매출액 합이 최대가 되는 경우는 [7, 6, 5, 10]입니다. 따라서 최대 매출액은 28입니다.

예시 #2
1일간 매출액 합이 최대가 되는 경우는 [5]입니다. 따라서 최대 매출액은 5입니다.

주어진 문제 9) 코드

def solution(revenue, k) :
    answer = 0
    rsum = sum(revenue[0:k])
    answer = rsum
    for i in range(len(revenue)) :
        rsum = rsum - revenue[i - k] + revenue[i]
        if answer < rsum :
            answer = rsum
    return answer

#아래는 테스트케이스 출력을 해보기 위한 코드입니다. 아래 코드는 잘못된 부분이 없으니, solution함수만 수정하세요.
revenue1 = [1, 1, 9, 3, 7, 6, 5, 10]
k1 = 4
ret1 = solution(revenue1, k1)

#[실행] 버튼을 누르면 출력 값을 볼 수 있습니다.
print("solution 함수의 반환 값은 ", ret1, " 입니다.")

revenue2 = [1, 1, 5, 1, 1]
k2 = 1
ret2 = solution(revenue2, k2)

#[실행] 버튼을 누르면 출력 값을 볼 수 있습니다.
print("solution 함수의 반환 값은 ", ret2, " 입니다.")

Solution

주어진 문제 9) Solution 코드

이번엔 빈칸 채우기, 함수 작성 문제가 아니라 코드 오류를 찾는 문제이다.
주어진 코드에서 한 줄만 변경해서 모든 입력에 대해 올바르게 동작하도록 수정하는 문제이다.

def solution(revenue, k) :
	answer = 0
	rsum = sum(revenue[0:k])
	answer = rsum
	for i in range(k, len(revenue)) : # 수정
		rsum = rsum - revenue[i - k] + revenue[i]
		if answer < rsum :
			answer = rsum
	return answer
    
#아래는 테스트케이스 출력을 해보기 위한 코드입니다. 아래 코드는 잘못된 부분이 없으니, solution함수만 수정하세요.
revenue1 = [1, 1, 9, 3, 7, 6, 5, 10]
k1 = 4
ret1 = solution(revenue1, k1)

#[실행] 버튼을 누르면 출력 값을 볼 수 있습니다.
print("solution 함수의 반환 값은 ", ret1, " 입니다.")

주어진 문제 9) Solution 코드 [본인 작성]

def solution(revenue, k) :
    answer = 0
    rsum = sum(revenue[0:k]) # 1. 처음부터 k번째 날짜까지 합을 구한다.
    answer = rsum
    for i in range(k, len(revenue)): # 2. k+1번째 날짜부터 마지막까지 돌면서 다음을 반복
        rsum = rsum - revenue[i-k] + revenue[i] # 3.1. (이전 합계 - 이전 윈도우의 맨 앞의 값 + 새로운 윈도우에 포함된 값)을 이용해 현재 윈도우의 합계를 구한다.

        answer = max(answer, rsum) # 3. 합계 중 큰 값을 찾는다.
    return answer

#아래는 테스트케이스 출력을 해보기 위한 코드입니다. 아래 코드는 잘못된 부분이 없으니, solution함수만 수정하세요.
revenue1 = [1, 1, 9, 3, 7, 6, 5, 10]
k1 = 4
ret1 = solution(revenue1, k1)

#[실행] 버튼을 누르면 출력 값을 볼 수 있습니다.
print("solution 함수의 반환 값은 ", ret1, " 입니다.")

revenue2 = [1, 1, 5, 1, 1]
k2 = 1
ret2 = solution(revenue2, k2)

#[실행] 버튼을 누르면 출력 값을 볼 수 있습니다.
print("solution 함수의 반환 값은 ", ret2, " 입니다.")

해당 문제는 슬라이딩윈도우 방식을 사용하여 매출액 리스트 revenue에서 연속된 k개의 매출액 합계가 최대인 값을 찾는 코드에서 잘못된 곳을 찾아 수정하는 문제이다.

다른 풀이 방식

1. 연속된 k 개의 합 중 최댓값 구하기 - 브루트 포스 방식

브루트 포스 방식 : 기준 항목을 선택한 후 중첩 for문을 이용하여 기준 항목부터 k개의 항목을 합산하여 연속된 k개의 합 중 최댓값을 찾는 방식이다. (완전 탐색)

예시

# 시작 : i인덱스 , 종료: i번 부터 4개
def solution(arr, k) :
    answer = 0

    for i in range(len(arr)-k+1) :
        rsum = 0
        for j in range(i,i+k):
            rsum+=arr[j]
        answer=max(answer,rsum)
    return answer

# 시작 : i인덱스 , 종료: i번 부터 갯수 4개를 세면서 합
def solution2(arr, k) :
    answer = 0
    for i in range(len(arr)-k+1) :
        rsum = 0
        for j in range(k):
            rsum+=arr[i+j]
        answer=max(answer,rsum)
    return answer

arr1 = [1, 1, 9, 3, 7, 6, 5, 10]
k1 = 4
ret1 = solution(arr1, k1)

print("solution 함수의 반환 값은 ", ret1, " 입니다.")

arr1 = [1, 1, 9, 3, 7, 6, 5, 10]
k1 = 4
ret1 = solution2(arr1, k1)

print("solution 함수의 반환 값은 ", ret1, " 입니다.")

→ 시간 복잡도 = $O(k*n)$

2. 연속된 k 개의 합 중 최댓값 구하기 - 슬라이딩 윈도우 방식

슬라이딩 윈도우 방식이란❓

일정한 너비의 창문을 옆으로 미는 것처럼 연속된 일정 개수의 항목을 이용하여 문제를 풀 때 사용하는 방법이다.

리스트 arr에서 연속된 4개의 항목 합계를 구하여 Four_sum에 저장한 후, 다음 4개의 항목 합을 구하기 위해서 Four_sum에서 arr[0]을 빼고, arr[4]를 더하면 원하는 값을 구할 수 있다.

연속된 k 개의 합 중 최댓값 구하기를 슬라이딩 윈도우 방식으로 푼다면❓

슬라이딩 윈도우 방식 : 처음 k개의 합계를 구한 뒤 for문을 이용해 반복하면서 이전에 구했던 합계 구간에서 이전 구간의 첫 번째 항목 값은 빼고 이전 구간의 바로 다음에 있는 항목값을 더하면서 연속된 k개의 합계 중 최댓값을 찾는 방식이다.

이전에 구한 합계 값 일부를 사용함으로써 반복되는 계산 횟수를 줄일 수 있다.

예시

def solution(arr, k) :
    answer = 0
    rsum = sum(arr[0:k])
    answer = rsum
    for i in range(k,len(arr)) :
        rsum = rsum - arr[i - k] + arr[i]
        answer=max(answer,rsum)
    return answer

arr1 = [1, 1, 9, 3, 7, 6, 5, 10]
k1 = 4
ret1 = solution(arr1, k1)


print("solution 함수의 반환 값은 ", ret1, " 입니다.")