슬라이딩 윈도우(sliding window) 문제: 폭탄해체하기

• k > 0: 배열의 i번째 숫자를 다음 **k**개의 숫자의 합으로 바꿉니다.예: code[i] = code[i+1] + code[i+2] + … + code[i+k]
• 원형 배열이므로 끝을 넘어서면 처음으로 돌아가 계산합니다.
• k : 배열의 i번째 숫자를 이전 **k**개의 숫자의 합으로 바꿉니다.예: code[i] = code[i-1] + code[i-2] + … + code[i+k]
• 원형 배열이므로 시작을 넘어서면 끝으로 돌아가 계산합니다.
• k == 0: 모든 숫자를 0으로 바꿉니다.즉, 결과는 [0, 0, …, 0].
• code: 길이 n의 정수 배열. (1 ≤ n ≤ 100)
• k: 정수 값. (-n k
• 암호화된 코드를 규칙에 따라 해독한 결과 배열.

Input: code = [5, 7, 1, 4], k = 3
Output: [12, 10, 16, 13]
Explanation:
- code[0] = 7 + 1 + 4 = 12
- code[1] = 1 + 4 + 5 = 10
- code[2] = 4 + 5 + 7 = 16
- code[3] = 5 + 7 + 1 = 13

예제 2

Input: code = [1, 2, 3, 4], k = 0
Output: [0, 0, 0, 0]
Explanation:
`k == 0`이므로 모든 숫자는 0으로 바뀝니다.

예제 3

Input: code = [2, 4, 9, 3], k = -2
Output: [12, 5, 6, 13]
Explanation:
- code[0] = code[3] + code[2] = 3 + 9 = 12
- code[1] = code[0] + code[3] = 2 + 3 = 5
- code[2] = code[1] + code[0] = 4 + 2 = 6
- code[3] = code[2] + code[1] = 9 + 4 = 13

• 이 문제의 중요한 점은 배열이 원형으로 연결되어 있다는 것입니다.
• 예를 들어, 배열의 마지막 요소 다음은 첫 번째 요소입니다:
• code[4]가 있다면 code[4 % n]은 code[0]입니다.
• 배열의 처음 이전 요소는 마지막 요소입니다:
• code[-1]은 code[n-1]과 같습니다.
• 슬라이딩 윈도우 기법을 활용하면, 각 숫자에 대해 중복 계산 없이 효율적으로 합을 구할 수 있습니다.
• 배열이 원형임을 고려해 인덱스를 처리할 때 mod 연산(% n)을 사용합니다.
• k > 0일 때 다음 숫자들의 합, k 일 때 이전 숫자들의 합을 계산해야 합니다.

• 단순히 매번 k개의 숫자를 반복적으로 더하면 비효율적입니다(시간 복잡도: O(n *

  k

  )).

• 슬라이딩 윈도우를 활용하면, 매번 윈도우를 조금씩 이동하며 덧셈/뺄셈 연산으로 효율적으로 합을 갱신할 수 있습니다(시간 복잡도: O(n)).

def decrypt(code, k):
    n = len(code)
    if k == 0:
        return [0] * n

    result = [0] * n
    window_sum = 0
    start, end = (1, k) if k > 0 else (n + k, n - 1)  # 슬라이딩 윈도우 범위 설정

    # 초기 윈도우의 합 계산
    for i in range(start, end + 1):
        window_sum += code[i % n]

    # 슬라이딩 윈도우를 이동하며 결과 계산
    for i in range(n):
        result[i] = window_sum
        # 윈도우를 오른쪽으로 한 칸 이동
        window_sum -= code[start % n]  # 윈도우 시작 값 제거
        start += 1
        end += 1
        window_sum += code[end % n]  # 윈도우 끝 값 추가

    return result

# 테스트
print(decrypt([5, 7, 1, 4], 3))   # 출력: [12, 10, 16, 13]
print(decrypt([1, 2, 3, 4], 0))   # 출력: [0, 0, 0, 0]
print(decrypt([2, 4, 9, 3], -2))  # 출력: [12, 5, 6, 13]

• start = 1, end = k로 초기 윈도우 범위를 설정합니다.
• 초기 윈도우 합을 계산한 뒤, 윈도우를 한 칸씩 오른쪽으로 이동하며:
• start 위치의 값을 빼고,
• end + 1 위치의 값을 더합니다.
• start = n + k, end = n - 1로 초기 윈도우 범위를 설정합니다(음수 방향 처리).
• start와 end는 원형 배열의 인덱싱을 위해 % n을 사용하여 순환하도록 만듭니다.
• 모든 결과값이 0이므로 [0] * n을 바로 반환합니다.
• O(n): 슬라이딩 윈도우를 사용하여 배열을 한 번만 순회합니다.
• O(1): 추가 메모리는 고정된 윈도우 합을 저장하는 데 사용됩니다.