Python으로 폭탄 해체용 암호 해독 프로그램 구현하기

문제 개요

폭탄을 해체해야 하는 아슬아슬한 상황을 상상해 보세요! 시간은 촉박하게 흐르는 가운데, 우리에게는 길이가 n인 원형 배열(circular array) code와 정수 키 k가 주어집니다. 암호를 해독하려면 배열의 모든 숫자를 동시에 새로운 값으로 교체해야 하며, 다음 세 가지 규칙을 따라야 합니다.

k > 0인 경우: i번째 숫자를 그 뒤에 있는 k개 숫자의 합으로 교체합니다.
k < 0인 경우: i번째 숫자를 그 앞에 있는 |k|개 숫자의 합으로 교체합니다.
k = 0인 경우: i번째 숫자를 단순히 0으로 교체합니다.

여기서 중요한 점은 배열이 원형이라는 것입니다. 즉, code[n-1]의 다음 요소는 code[0]이 되고, code[0]의 이전 요소는 code[n-1]이 됩니다. 최종적으로 해독된 배열을 반환하면 폭탄이 무사히 해체됩니다.

예시로 이해하기

입력이 code = [8, 2, 3, 5], k = 3이라고 가정해 보겠습니다. 각 위치를 다음 3개 요소의 합으로 교체해야 하므로 출력은 [10, 16, 15, 13]이 됩니다.

code[0]: 2 + 3 + 5 = 10
code[1]: 3 + 5 + 8(순환) = 16
code[2]: 5 + 8 + 2(순환) = 15
code[3]: 8 + 2 + 3(순환) = 13

해결 알고리즘

이 문제는 모듈로(%) 연산을 활용해 배열의 순환 구조를 처리하면 손쉽게 해결할 수 있습니다. 접근 방법은 다음과 같습니다.

결과를 저장할 빈 리스트 decode를 생성합니다.
i를 0부터 배열 길이 - 1까지 반복하면서 다음을 수행합니다.
- k > 0이면: 합계 sum을 0으로 초기화하고, j를 i+1로 설정한 뒤 k번만큼 code[j mod len(code)] 값을 더하며 j를 1씩 증가시킵니다.
- k = 0이면: decode에 0을 추가합니다.
- k < 0이면: j를 i-1로 설정한 뒤 |k|번만큼 code[j mod len(code)] 값을 더하며 j를 1씩 감소시킵니다.
모든 위치가 처리되면 decode를 반환합니다.

Python 구현 예제

아래 코드를 통해 실제 구현 방법을 확인해 보세요.

def solve(code, k):
    decode = []
    for i in range(len(code)):
        if k > 0:
            sum = 0
            j = i + 1
            m = k
            while(m):
                sum += code[j % len(code)]
                m -= 1
                j += 1
            decode.append(sum)

        elif k == 0:
            decode.append(0)

        else:
            sum = 0
            j = i - 1
            m = k
            while(m):
                sum += code[j % len(code)]
                m += 1
                j -= 1
            decode.append(sum)

    return decode

code = [8, 2, 3, 5]
k = 3
print(solve(code, k))

입력

[8, 2, 3, 5], 3

출력

[10, 16, 15, 13]

복잡도 분석

시간 복잡도: O(n × |k|) — 각 원소마다 최대 |k|개의 값을 더하기 때문입니다.
공간 복잡도: O(n) — 결과를 저장할 리스트가 필요합니다.

참고로 슬라이딩 윈도우 기법을 활용하면 인접 두 결과 값의 차이만 계산하여 시간 복잡도를 O(n)까지 줄일 수 있습니다. 다만 위의 직관적인 구현 역시 문제 제약 조건 내에서 충분히 효율적으로 동작합니다.