[LeetCode] 848. Shifting Letters

문제 출처: https://leetcode.com/problems/shifting-letters/

Shifting Letters - LeetCode

---

문제

영어 소문자로 이루어진 문자열 $s$와 동일한 길이의 정수 배열 $shifts$가 주어진다. 한 문자에서 shift()를 호출하면, 알파벳에서 다음 단어를 호출한다.

• 예를 들어, shift('a') = 'b', shift('t') = 'u', 그리고 shift('z') = 'a'

 

각 $shift[i] = x$에 대해서, 첫 $i+1$개의 문자를 $x$번 이동시키려고 한다.

 

모든 $shifts$를 적용시킨 후, 최종 문자열을 반환하라.

예제

Input: s = "abc", shifts = [3,5,9]
Output: "rpl"

Explanation: We start with "abc".
After shifting the first 1 letters of s by 3, we have "dbc".
After shifting the first 2 letters of s by 5, we have "igc".
After shifting the first 3 letters of s by 9, we have "rpl", the answer.

Input: s = "aaa", shifts = [1,2,3]
Output: "gfd"

---

풀이

아무런 방법을 쓰지 않고, shifts를 순차적으로 읽으면서 shifts[i]를 s에 적용하기 위해서 s의 첫 (i+1)개의 문자를 변경해 간다고 생각해보자. 다음의 표와 같이 각 인덱스 i 마다 (i+1)개의 문자를 수정해야 하는 과정이 필요하고, 이는 총 $\frac{n(n+1)}{2}$ 번의 반복이 필요함을 의미한다.

shifts[i]'s i	shifts[i]만큼 이동해야 하는 s의 인덱스(개수)
0	0 (1개)
1	0, 1 (2개)
2	0, 1, 2 (3개)
...	...
n	0, 1, 2, ..., n (n개)
총 누적	n(n+1) / 2

s의 최대 길이가 $10^5$임을 감안하면, 약 50억 만큼의 반복이 필요하다는 이야기가 되므로 이보다 효율적인 방법을 생각해 내야 한다.

 

위에서는 shifts[i]가 적용되어야 하는 s의 문자를 살펴봤다면, 반대로 s[i]에 적용되는 shifts값을 구해보자.

s[i]의 i 값	s[i]에 적용되야 하는 shifts
0	0, 1, 2, ..., n (n개)
1	1, 2, ..., n (n-1개)
2	2, ..., n (n-2개)
...	...
n	n (1개)

표 안에 적혀진 반복 횟수 이전과 다를 바가 없다. 여기서 한 가지 최적화 포인트가 있는데, s[i]에 적용되어야 하는 shifts 값을 미리 계산해 놓는 것이다.

 

다음 코드와 같이 shifts 배열을 뒤에서부터 앞으로 누적시키는 것으로 O(n) 만에 각 s[i]에 적용되어야 하는 최종 shifts 값을 계산할 수 있다.

var shiftingLetters = function(s, shifts) {
    const cntShift = Array(shifts.length).fill(0);
    
    cntShift[shifts.length-1] = shifts[shifts.length-1]
    
    for (let i = shifts.length-2; i >= 0; i--) {
        cntShift[i] = shifts[i] + cntShift[i+1];
    }
};

이와 같이 s[i]에 적용되어야 하는 shifts의 값을 미리 계산해 놓는다면, s[i]당 한 번의 계산으로 최종 shift 이동한 문자를 얻을 수 있다.

 

이제 각 s[i]를 정해진 횟수만큼 shift하는 연산을 생각해보면, 우선, 'a' ~ 'z'를 [0, 25]으로 대응시킨다. 알파벳이 대응되는 숫자에 이동시킬 값만큼을 더하고 26으로 나눈 나머지를 취한다. 이 값이 가리키는 문자가 얻고자 하는 문자가 된다.

var shiftingLetters = function(s, shifts) {
    const cntShift = Array(shifts.length).fill(0);
    
    cntShift[shifts.length-1] = shifts[shifts.length-1]
    
    for (let i = shifts.length-2; i >= 0; i--) {
        cntShift[i] = shifts[i] + cntShift[i+1];
    }
    
    let answer = '';
    
    const a = 'a'.charCodeAt(0);
    for (let i = 0; i < shifts.length; i++) {
        let alphabet = s[i].charCodeAt(0) - a;
        alphabet += cntShift[i];
        alphabet %= 26;
        answer += String.fromCharCode(alphabet + a);
    }
    
    return answer;
};

최종적으로 이 방식의 시간 복잡도를 생각하면, 각 문자가 이동할 횟수를 계산하는데 O(n)이 소요되고, 각 문자에 대해 이동 결과를 만드는데 O(n)이 소요되므로 최종적으로 O(n)의 시간 복잡도를 갖는다고 말할 수 있다.

 

Github: 848.js

GitHub - opwe37/Algorithm-Study