LeetCode [1652]: Defuse the Bomb

📌 LeetCode [1652]: Defuse the Bomb

🔗 문제 링크

---

문제 설명 📄

정수 배열 code와 정수 k가 주어집니다. 배열 code는 원형으로 연결된 형태로 동작하며, 배열의 각 원소를 특정 규칙에 따라 암호화 해제해야 합니다.

• k > 0: 현재 위치에서 오른쪽으로 k개의 요소의 합을 구합니다.
• k < 0: 현재 위치에서 왼쪽으로 |k|개의 요소의 합을 구합니다.
• k == 0: 배열의 모든 값은 0으로 설정됩니다.

code의 암호 해제된 배열을 반환하세요.

---

문제 해결 접근 💡

1. 문제를 단순화하기:
   • k의 값이 양수/음수/0인 경우를 분리해서 해결합니다.
   • 양수일 경우: 오른쪽으로 이동하며 합 계산.
   • 음수일 경우: 왼쪽으로 이동하며 합 계산.
   • k == 0일 경우: 모든 값을 0으로 설정.
2. 효율적인 계산:
   • 배열의 길이를 초과하여 접근하는 경우, 모듈로 연산 (i + j) % len(code)를 이용해 인덱스를 조정합니다.
   • 왼쪽으로 이동하는 경우 (i - j) % len(code)를 사용합니다.
3. 시간 복잡도:
   • k에 따라 각 원소를 순회하며, 내부 루프에서 최대 ( O(|k|) ) 연산이 수행됩니다.
   • 최종 시간 복잡도: ( O(n \cdot |k|) ), ( n )은 배열 code의 길이.

---

Solution 💻

class Solution:
    def decrypt(self, code: List[int], k: int) -> List[int]:
        answer = []

        if k > 0:
            for i in range(len(code)):
                hap = 0
                for j in range(1, k + 1):
                    hap += code[(i + j) % len(code)]
                answer.append(hap)
        elif k < 0:
            for i in range(len(code)):
                hap = 0
                for j in range(1, abs(k) + 1):
                    hap += code[(i - j) % len(code)]
                answer.append(hap)
        else:
            answer = [0 for _ in range(len(code))]

        return answer

시간 복잡도 ⏲️

• 루프 순회: 배열의 각 원소에 대해 ( n )회 반복.
• 내부 루프: ( k )의 절대값만큼 반복.
• 총 시간 복잡도: ( O(n \cdot |k|) ).

공간 복잡도 🗄️

• 결과 배열: ( O(n) ), 배열의 길이만큼 공간 사용.
• 총 공간 복잡도: ( O(n) ).

---

리팩토링 🛠️

개선된 코드

class Solution:
    def decrypt(self, code: List[int], k: int) -> List[int]:
        n = len(code)
        if k == 0:
            return [0] * n

        result = [0] * n
        step = 1 if k > 0 else -1
        k = abs(k)

        for i in range(n):
            result[i] = sum(code[(i + j * step) % n] for j in range(1, k + 1))

        return result

리팩토링 후 시간 복잡도 ⏲️

• 내부 루프가 sum()을 사용하여 간결화되었지만, 시간 복잡도는 동일하게 ( O(n \cdot |k|) )입니다.

리팩토링 후 공간 복잡도 🗄️

• 기존과 동일한 ( O(n) )입니다.