[LeetCode # 848] Shifting Letters

주어진 문제는 n 의 길이를 갖는 문자열과 정수 배열이 주어졌을 때, 특정 조건에 맞게 문자열을 shift 한 결과를 반환하는 것이다.

 

위의 <예제 1> 을 가지고 설명을 하자면 문자열 "abc" 와 정수 배열 {3, 5, 9} 가 주어졌을 때, 앞에서부터 부분 문자열 "a" 에 shift() 연산을 세 번 수행해 "dbc" 라는 문자열을 만들고, 그 다음은 "db" 에 대해 shift() 를 수행해 "igc" 를 만든 뒤 마지막으로 "igc" 에 대해 shift() 를 수행해 "rpl" 이라는 문자열을 만든다.

 

즉, 각 자리 별로 i 번째 자리의 문자는 총 shifts[i] + shifts[i + 1] + ... + shifts[n - 1] 만큼 shift() 연산을 수행하게 된다. 이 문제를 해결하기 위해 적용한 해결 방법은 맨 마지막 자리부터 shift() 연산을 수행하는 것이다.

 

'n - 1' 번째 문자는 shifts[n - 1] 만큼만 shift() 연산을 수행하므로 이를 수행하고 역순으로 shifts 값을 누적시키며 shift() 연산을 수행하도록 하면 문제를 해결할 수 있을 거라 생각했다. 또한, 주어진 조건에 shifts[i] 는 최대 10억의 값을 가질 수 있는데 shift() 연산의 결과는 항상 영어 소문자이므로 'a' ~ 'z' 까지만의 shift 만 가능하고 shift() 연산의 결과는 26번을 기준으로 동일하기 때문에 shifts[i] 의 값을 26 으로 나눈 나머지값을 가지고 shift() 를 수행하도록 했다.

 

추가적으로 25번의 shift 를 각 자리별로 일일히 수행하게 될 경우, 이 또한 불필요한 연산을 반복한다 생각했다. 현재 문자가 몇 번째 소문자인지만 확인한 뒤 몇 번의 shift 를 수행하는 지만 확인하면 되기 때문이다. 예를 들어, 'a' 라는 문자는 0 번째 소문자이고 5번의 shift() 연산을 수행한다면 'f' 라는 문자로 치환할 수 있다. 이러한 방식으로 문제를 해결할 수 있었고, 문제의 해결에 사용한 코드는 다음과 같다.

 

class Solution {
public:
    string shiftingLetters(string s, vector<int>& shifts) {
        int sum = 0;
        for (int i = s.size() - 1; i >= 0; i--) {
            sum = (sum + shifts[i]) % 26;
            s[i] = (s[i] - 'a' + sum) % 26 + 'a';
        }
        return s;
    }
};