[백준] 21921번: 블로그

https://www.acmicpc.net/problem/21921

initial

After solving (actually googled for solution but anyway) https://velog.io/@whitehousechef/%EB%B0%B1%EC%A4%80-12891%EB%B2%88-DNA-%EB%B9%84%EB%B0%80%EB%B2%88%ED%98%B8

I tried to handle my initialised sliding window inside the main logic for cleaner code. Rmb it has to be incomplete sliding window for this to work

my correct solution

n,k = map(int,input().split())
lst = list(map(int,input().split()))
window = lst[:k-1]
ans = sum(window)
tmp=[]
left,right = 0,k-1
while right <n:
    ans += lst[right]
    tmp.append(ans)
    ans -= lst[left]
    left+=1
    right+=1
if ans==0:
    print("SAD")
else:
    print(max(tmp))
    print(tmp.count(max(tmp)))

complexity

The provided code appears to find the maximum sum of consecutive subarrays of length k within a given list lst, and it also counts how many times this maximum sum occurs. Here's the complexity analysis of the code:

1. Input Reading (Linear Time):

   • Reading n and k takes constant time.
   • Reading the list lst with n elements using list(map(int, input().split())) takes linear time, O(n), as it processes each element in the list.

2. Initialization (Constant Time):

   • Creating the initial window list of size k-1 takes constant time since it depends on k.

3. Sliding Window (Linear Time):

   • The code uses a sliding window approach to compute the maximum sum of consecutive subarrays of length k.
   • The loop iterates through the list lst from index k-1 to n-1, which results in n - (k-1) iterations.
   • For each iteration, it computes the sum of the elements in the current window (window) and updates the ans variable.
   • It also appends the current ans to the tmp list.
   • Both the sum calculation and list appending are constant time operations.
   • Therefore, the sliding window part has a time complexity of O(n - (k-1)), which simplifies to O(n) since k is a constant.

4. Printing (Linear Time):

   • The code prints the maximum sum (max(tmp)) and counts how many times it occurs (tmp.count(max(tmp)).
   • Counting the occurrences using tmp.count(max(tmp)) has a time complexity of O(n) because it needs to scan the entire tmp list.

Overall, the most time-consuming part of the code is the sliding window computation, which has a time complexity of O(n). Therefore, the overall time complexity of the code is O(n).

The space complexity is also O(n) because of the tmp list, which stores the results for each window. The other variables and lists used in the code have constant space requirements.