소문자로만 이루어진 문자열 s와, s와 길이가 같은 정수 리스트 shifts가 있다고 가정해 보겠습니다. shifts[i]의 각 원소는 s의 첫 i + 1개 문자(인덱스 0부터 i까지)를 shifts[i]칸씩 밀라는 명령을 의미합니다. 이동 중 'z'를 넘어가면 다시 'a'로 순환됩니다. 목표는 모든 이동 명령을 s에 적용한 뒤의 최종 문자열을 구하는 것입니다.
예를 들어 입력이 s = "tomato", shifts = [2, 5, 2, 3, 7, 4]라고 해보겠습니다. 첫 번째 문자를 2칸 밀면 't'가 'v'가 되어 문자열은 "vomato"가 됩니다. 이어서 앞 두 문자를 각각 5칸씩 밀면 "atmato"가 되고, 같은 방식으로 나머지 명령을 차례로 적용하면 최종 결과는 "qjcoes"가 됩니다.
문제 해결 접근 방식
매번 처음부터 모든 문자를 다시 이동시키면 비효율적입니다. 대신 핵심 관찰 하나를 활용할 수 있습니다. shifts[i]는 인덱스 i까지의 모든 문자에 공통으로 적용되므로, 특정 위치의 문자에 실제로 가해지는 총 이동량은 해당 위치부터 마지막 원소까지의 누적합(접미사 합)과 같습니다. 따라서 다음 단계로 문제를 해결할 수 있습니다.
- start := 'a'의 아스키 코드 값
- res := s의 각 문자를 'a' 기준 상대값(ord(i) - start)으로 변환한 리스트
- i를 len(shifts) - 2부터 0까지 1씩 감소시키며 반복
- shifts[i] := shifts[i] + shifts[i + 1] (뒤에서부터 누적 이동량 계산)
- i를 0부터 len(s) - 1까지 반복
- c := (res[i] + shifts[i]) mod 26
- res[i] := 아스키 코드가 (c + start)인 문자
- res의 문자들을 하나의 문자열로 결합하여 반환
이 방식은 각 문자를 한 번씩만 처리하므로 시간 복잡도 O(n), 추가 공간 복잡도 O(n)으로 문제를 효율적으로 해결할 수 있습니다.
예제 코드
다음 파이썬 구현을 통해 더 자세히 이해해 보겠습니다.
def solve(s, shifts):
start = ord("a")
res = [ord(i) - start for i in s]
for i in range(len(shifts) - 2, -1, -1):
shifts[i] += shifts[i + 1]
for i in range(len(s)):
c = (res[i] + shifts[i]) % 26
res[i] = chr(c + start)
return "".join(res)
s = "tomato"
shifts = [2, 5, 2, 3, 7, 4]
print(solve(s, shifts))
입력
s = "tomato", shifts = [2, 5, 2, 3, 7, 4]
출력
qjcoes