[Leetcode/Sliding Window] 1652. Defuse the Bomb

🔍 슬라이딩 윈도우(Sliding Window)

• 배열에서 부분 합을 효율적으로 계산하는 기법
• 매번 전체 합을 다시 계산하지 않고, 최초 윈도우의 합을 미리 계산해둔 후 기존 윈도우의 값을 조금씩 변경하면서 업데이트한다.
• 즉, 현재 합에서 빠질 값과 추가할 값만 업데이트하면 O(1) 시간에 갱신이 가능한 효율적 알고리즘이다! 

class Solution:
    def decrypt(self, code: List[int], k: int) -> List[int]:
        n = len(code)  # 원래 코드 배열의 길이
        
        # k가 0이면 모든 원소를 0으로 변경
        if k == 0:
            return [0] * n
        
        # Extend code to handle circular array easily
        code_extended = code * 2  # 예: [2,4,9,3] -> [2,4,9,3,2,4,9,3]
        
        result = [0] * n  # 결과를 저장할 배열

        # 슬라이딩 윈도우의 시작점과 끝점 결정
        # k > 0: 현재 원소의 다음 k개의 합을 구해야 함
        # k < 0: 현재 원소의 이전 k개의 합을 구해야 함
        start, end = (1, k) if k > 0 else (n + k, n - 1)

        # Initial sum of the first window
        window_sum = sum(code_extended[start:end + 1])

        # 원래 배열의 각 원소에 대해 슬라이딩 윈도우 적용
        for i in range(n):
            result[i] = window_sum  # 현재 윈도우 합을 결과 배열에 저장
            
            # Slide the window forward
            window_sum -= code_extended[start]  # 현재 윈도우에서 가장 왼쪽 원소 제거
            window_sum += code_extended[end + 1]  # 새롭게 포함될 원소 추가

            start += 1
            end += 1

        return result

• start, end = (1, k) if k > 0 else (n + k, n - 1):
  • k > 0이면 현재 원소의 다음 k개를 더해야 하므로 start = 1, end = k.
    • start = 1: 현재 인덱스 i에서 1칸 오른쪽으로 이동한 값부터 합산 시작
    • end = k: 현재 인덱스 i에서 오른쪽 k번째까지 포함
    • 즉, i의 오른쪽 k개의 숫자를 슬라이딩 윈도우로 합산
  • k < 0이면 현재 원소의 이전 k개를 더해야 하므로 start = n + k, end = n - 1.
    • 현재 숫자를 기준으로 왼쪽 방향으로 |k|개의 숫자를 더해야 함
    • start = n + k:
      • 예를 들어, code = [2, 4, 9, 3], k = -2 ----->  n = 4, k = -2이면 start = 4 - 2 = 2
      • 즉, 현재 인덱스 i에서 왼쪽 |k|개 전 위치의 인덱스부터 시작
    • end = n - 1:
      • n = 4이면 end = 3
      • 즉, 현재 원소 바로 왼쪽(이전 원소)까지 포함
    • 즉, i의 왼쪽 |k|개의 숫자를 슬라이딩 윈도우로 합산
• window_sum = sum(code_extended[start:end + 1]):
  • 첫 번째 원소에 대해 k개의 합을 미리 계산.

📌 예제 적용

1️⃣ code = [5,7,1,4], k = 3

• start = 1, end = 3
• window_sum = sum(code_extended[1:4]) → 다음 3개의 숫자 합

2️⃣ code = [2,4,9,3], k = -2

• start = 4 - 2 = 2, end = 4 - 1 = 3
• window_sum = sum(code_extended[2:4]) → 이전 2개의 숫자 합

---

⏳ 시간 복잡도 분석

• 초기 window_sum 계산: O(k)
• 슬라이딩 윈도우 업데이트: O(n)
• 총 시간 복잡도: O(n)