문제 링크

내 코드

해설 참고.

Solution

Approach: Difference Array

• 176ms, 15.95MB
• Complexity
  • Let $n$ be the size of the string s and $m$ the size of the shifts array.
  • Time Complexity: $O(n + m)$
  • Space Complexity: $O(n)$

class Solution {
public:
    string shiftingLetters(string s, vector<vector<int>>& shifts) {
        int n = s.size();
        vector<int> diffArray(
            n, 0);  // Initialize a difference array with all elements set to 0.

        for (auto shift : shifts) {
            if (shift[2] == 1) {        // If direction is forward (1):
                diffArray[shift[0]]++;  // Increment at the start index to
                                        // indicate a forward shift.
                if (shift[1] + 1 < n) {
                    diffArray[shift[1] +
                              1]--;  // Decrement at the end+1 index to stop the
                                     // effect of the shift.
                }
            } else {                    // If direction is backward (0):
                diffArray[shift[0]]--;  // Decrement at the start index to
                                        // indicate a backward shift.
                if (shift[1] + 1 < n) {
                    diffArray[shift[1] +
                              1]++;  // Increment at the end+1 index to stop the
                                     // effect of the shift.
                }
            }
        }

        string result(n, ' ');
        int numberOfShifts = 0;

        for (int i = 0; i < s.size(); i++) {
            numberOfShifts = (numberOfShifts + diffArray[i]) %
                             26;  // Update cumulative shifts, keeping within
                                  // the alphabet range.
            if (numberOfShifts < 0)
                numberOfShifts +=
                    26;  // Ensure `numberOfShifts` is non-negative.

            // Calculate the new character by shifting `s[i]`
            result[i] = 'a' + (s[i] - 'a' + numberOfShifts) % 26;
        }

        return result;
    }
};

GPT

이 코드는 “Difference Array” 기법을 사용하여 여러 범위 시프트 연산을 O(n)으로 최적화하는 문제 해결 방법을 보여줍니다.
즉, 여러 개의 시프트 연산을 단순 반복하지 않고 효율적으로 누적하여 한 번만 처리합니다.

---

🔍 문제 개요

• 주어진 문자열 s에 대해 여러 개의 시프트 연산(shifts[i] = [start, end, direction])이 주어짐.
• 각 shifts[i]는 s[start] ~ s[end] 범위를 시프트:
  • direction == 1 → 오른쪽(+) 시프트
  • direction == 0 → 왼쪽(-) 시프트
• 모든 시프트 연산을 반영한 최종 문자열을 반환해야 함.

---

📌 코드 분석

1️⃣ Difference Array (차분 배열) 생성

vector<int> diffArray(n, 0); // 차분 배열 초기화 (모든 값 0)

• diffArray[i]는 s[i]에 적용할 총 시프트 변화량을 나타냄.
• 여러 개의 시프트를 O(n)으로 빠르게 반영하기 위해 사용됨.

---

2️⃣ 시프트 연산 반영 (차분 배열 업데이트)

for (auto shift : shifts) {
    if (shift[2] == 1) {  // 오른쪽(+) 시프트
        diffArray[shift[0]]++;
        if (shift[1] + 1 < n) {
            diffArray[shift[1] + 1]--;
        }
    } else {  // 왼쪽(-) 시프트
        diffArray[shift[0]]--;
        if (shift[1] + 1 < n) {
            diffArray[shift[1] + 1]++;
        }
    }
}

• diffArray[start]++: start부터 시프트 적용 시작
• diffArray[end + 1]--: end + 1부터 시프트 중단
• 이 방식은 누적합을 이용하여 O(n)만에 모든 시프트를 적용 가능

✅ O(n)으로 모든 시프트 연산 반영 가능!

---

3️⃣ 누적합을 이용해 최종 시프트 값 계산

string result(n, ' '); // 최종 결과 문자열
int numberOfShifts = 0;

for (int i = 0; i < s.size(); i++) {
    numberOfShifts = (numberOfShifts + diffArray[i]) % 26;  // 누적합 계산
    if (numberOfShifts < 0) numberOfShifts += 26;  // 음수 방지

• 누적합을 사용하여 각 문자에 적용할 최종 시프트 값(numberOfShifts)을 계산
• (numberOfShifts + diffArray[i]) % 26을 사용하여 알파벳 범위 내에서 반복
• 음수가 되지 않도록 +26을 추가하여 조정

✅ O(n)으로 모든 문자에 대해 최종 시프트 값 적용 가능!

---

4️⃣ 최종 문자 변환 및 반환

    result[i] = 'a' + (s[i] - 'a' + numberOfShifts) % 26;
}

return result;

• s[i] - 'a': s[i]를 숫자로 변환 (a=0, b=1, ... z=25)
• + numberOfShifts: 누적된 시프트 값 적용
• % 26: 알파벳 범위를 유지
• 'a' + ...: 다시 문자로 변환

✅ 모든 문자에 대해 한 번만 변환하므로 O(n)으로 해결!

---

📌 예제 실행

string s = "abc";
vector<vector<int>> shifts = { {0, 1, 1}, {1, 2, 1}, {0, 2, 0} };
Solution sol;
cout << sol.shiftingLetters(s, shifts);

Step 1: 초기 차분 배열 생성

s	a	b	c
Index	0	1	2
diffArray 초기값	0	0	0

Step 2: 차분 배열 업데이트

(1) shifts[0] = {0, 1, 1} (0~1 오른쪽 시프트)

• diffArray[0]++ → [1, 0, 0]
• diffArray[2]-- → [1, 0, -1]

(2) shifts[1] = {1, 2, 1} (1~2 오른쪽 시프트)

• diffArray[1]++ → [1, 1, -1]
• diffArray[3]-- (무시)

(3) shifts[2] = {0, 2, 0} (0~2 왼쪽 시프트)

• diffArray[0]-- → [0, 1, -1]
• diffArray[3]++ (무시)

✅ 최종 diffArray = [0, 1, -1]

---

Step 3: 누적합 계산

Index	0	1	2
diffArray	0	1	-1
numberOfShifts (누적)	0	1	0

---

Step 4: 최종 문자 변환

Index	s[i]	Shifted (s[i] + numberOfShifts)	결과
0	'a'	'a' + 0 = 'a'	'a'
1	'b'	'b' + 1 = 'c'	'c'
2	'c'	'c' + 0 = 'c'	'c'

✅ 최종 출력: "acc"

---

⏱ 시간 복잡도 분석

연산	시간 복잡도
차분 배열 초기화	O(n)
시프트 적용 (shifts 순회)	O(m) (m = shifts.size())
누적합 계산	O(n)
최종 문자 변환	O(n)
전체 시간 복잡도	$O(n + m)$

✅ 매우 효율적인 O(n + m) 해결법! 🚀

---

💡 핵심 최적화 포인트

1. 차분 배열(Difference Array) 사용 → O(n) 만에 시프트 적용 가능
2. 누적합(Prefix Sum) 활용 → 한 번의 O(n) 반복으로 빠르게 시프트 반영
3. 모든 문자를 한 번만 업데이트 → O(n) 이내에 최종 문자열 변환

---

✅ 결론

✔ O(n + m)으로 최적화된 Difference Array 기법 사용
✔ 문자열 변환 문제에서 시프트 연산을 빠르게 처리하는 핵심 기법! 🚀
✔ shifts가 많아도 빠른 실행이 가능 ✅
✔ 알고리즘 면접에서도 유용한 테크닉! 🎯