[LeetCode] 848. Shifting Letters

문제

소문자로 이루어진 문자열 s와 같은 길이의 정수 배열 shifts가 주어진다.

shifts[i] = x는 s의 앞에서부터 i + 1개 문자를 각각 알파벳 순서로 x번 민다는 뜻이다. ('z' 다음은 다시 'a')

모든 시프트를 적용한 최종 문자열을 반환한다.

예시

입력: s = "abc", shifts = [3, 5, 9]
출력: "rpl"

• shifts[0] = 3 → 앞 1글자를 3번: "dbc"
• shifts[1] = 5 → 앞 2글자를 5번: "igc"
• shifts[2] = 9 → 앞 3글자를 9번: "rpl"

제약

• 1 <= s.length <= 10^5
• 0 <= shifts[i] <= 10^9

접근

그대로 시뮬레이션하면?

shifts[i]마다 앞의 i + 1글자를 전부 갱신하면 O(n²)이다. 길이가 10^5라 최악의 경우 약 50억 번 연산이 되어 시간 초과가 난다.

관점 바꾸기: 각 문자가 몇 번 밀리는가

i번째 문자는 shifts[i], shifts[i + 1], ..., shifts[n - 1]에 모두 영향을 받는다. 즉 i번째 문자가 밀리는 횟수 = shifts[i..n-1]의 합(접미사 합)이다.

s      =  a   b   c
shifts =  3   5   9
접미사합 = 17  14   9
결과    =  r   p   l

뒤에서부터 순회하면서 합을 누적하면 한 번의 순회로 모든 문자의 이동량을 구할 수 있다.

나머지 연산

알파벳은 26개라 26번 밀면 제자리다. 그래서 누적할 때마다 % 26을 해 둔다. shifts[i]가 최대 10^9이고 길이가 10^5라 합이 10^14까지 커질 수 있는데, 매번 나머지를 취하면 값이 항상 26 미만으로 유지된다.

풀이

function shiftingLetters(s: string, shifts: number[]): string {
    const ALPHABET_LEN = 26;
    const START_CODE = 97; // 'a'

    // 문자를 0~25 숫자로 변환
    const code = [...s].map(char => char.charCodeAt(0) - START_CODE);

    // 뒤에서부터 접미사 합을 누적하며 각 문자에 적용
    let shiftSum = 0;
    for (let i = s.length - 1; i >= 0; i--) {
        shiftSum = (shiftSum + shifts[i]) % ALPHABET_LEN;
        code[i] = (code[i] + shiftSum) % ALPHABET_LEN;
    }

    // 다시 문자로 변환
    return code.map(c => String.fromCharCode(c + START_CODE)).join('');
}

1. 문자를 'a' 기준 0~25 숫자로 바꾼다.
2. 마지막 인덱스부터 shiftSum에 shifts[i]를 더해 접미사 합을 만든다.
3. 현재 문자에 shiftSum을 더하고 26으로 나눈 나머지를 취한다.
4. 숫자를 다시 문자로 바꿔 이어 붙인다.

복잡도

• 시간: O(n), 문자열을 한 번 순회한다.
• 공간: O(n), 문자 코드 배열을 둔다.

정리

"앞에서 i + 1개를 민다"는 조건을 시프트 기준이 아니라 문자 기준으로 뒤집어 보면 접미사 합 문제가 된다. 범위 갱신이 반복되는 문제를 만나면 각 원소가 받는 영향의 합을 누적합으로 한 번에 구할 수 있는지 먼저 보는 게 좋다.