문제 개요
소문자로만 구성된 문자열 S와 정수 배열 shifts가 주어진다고 가정해 봅시다. 여기서 문자를 한 번 이동(shift)한다는 것은 알파벳상에서 다음 글자로 바꾸는 것을 의미하며, 특별히 'z'를 이동시키면 'a'가 됩니다. 각 shifts[i] = x에 대해 문자열 S의 앞에서부터 i+1번째 문자까지를 각각 x번 이동시켜야 하며, 모든 이동 연산을 적용한 뒤의 최종 문자열을 구하는 것이 목표입니다.
예를 들어 문자열이 "abc"이고 shifts = [3, 5, 9]라고 해보겠습니다.
- 첫 번째 문자 1개('a')를 3번 이동 → "dbc"
- 앞의 두 문자를 각각 5번 이동 → "igc"
- 세 문자 전체를 각각 9번 이동 → "rpl" (최종 결과)
접근 방법
핵심 아이디어는 뒤에서부터의 누적합(suffix sum)입니다. i번째 문자는 shifts[0]부터 shifts[i]까지의 모든 값의 영향을 받기 때문에, 배열을 뒤에서 앞으로 순회하며 각 위치의 총 이동 횟수를 미리 계산해 둘 수 있습니다. 값이 지나치게 커지는 것을 방지하기 위해 매 단계마다 26으로 나눈 나머지를 취합니다.
- shifts 배열의 끝에서 두 번째 원소부터 인덱스 0까지 역순으로 순회하며 다음을 수행합니다.
- shifts[i] = shifts[i] + shifts[i + 1]
- shifts[i] = shifts[i] % 26
- 인덱스 0부터 S의 길이 - 1까지 순회하며 각 문자를 해당 횟수만큼 이동합니다.
- S[i] = ((S[i] - 'a'의 ASCII 값) + shifts[i] % 26) + 'a'의 ASCII 값
- 변환이 완료된 문자열 S를 반환합니다.
C++ 구현 예제
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
string shiftingLetters(string S, vector<int>& shifts) {
for(int i = shifts.size() - 2 ;i >=0; i--){
shifts[i] += shifts[i + 1];
shifts[i] %= 26;
}
for(int i = 0; i < S.size(); i++) {
S[i] = ( ((S[i] - 'a') + shifts[i]) % 26 + 'a');
}
return S;
}
};
main(){
vector<int> v = {3,5,9};
Solution ob;
cout << (ob.shiftingLetters("abc", v));
}입력
"abc"
[3,5,9]
출력
rpl
복잡도 분석
시간 복잡도: O(n) — 배열을 두 번 순회하므로 문자열 길이에 비례합니다.
공간 복잡도: O(1) — 입력으로 주어진 shifts 배열을 그대로 재활용하여 추가 메모리를 사용하지 않습니다.
이처럼 뒤에서부터의 누적합을 활용하면 각 문자마다 이동 횟수를 반복해서 더하는 비효율적인 O(n²) 방식을 피하고, 선형 시간 안에 문제를 깔끔하게 해결할 수 있습니다.