[DSA] 투 포인터

---

---

개요

투 포인터는 배열과 문자열 문제를 해결하기 위해 자주 사용되는 기법이다. 이 방법은 반복 가능한 구조를 따라 이동하는 두 개의 정수 변수를 사용하는 것을 포함한다. 이 글에서는 배열과 문자열에 초점을 맞추고 있다. 여기에는 i와 j 또는 left와 right와 같은 두 정수가 주로 사용되는데, 이들은 배열 또는 문자열의 인덱스를 나타낸다.

투 포인터를 구현하는 방법은 여러 가지가 있다. 시작하기 위해, 다음 방법을 살펴보자:

포인터를 입력의 가장자리 양쪽에서 시작한다. 그들이 서로 만날 때까지 서로를 향해 이동한다.

이 개념을 구체적인 단계로 나누면 다음과 같다:

1. 하나의 포인터는 첫 번째 인덱스 0에서, 다른 포인터는 마지막 인덱스 input.length - 1에서 시작한다.
2. 포인터가 서로 같아질 때까지 while 문을 사용한다.
3. 루프의 각 반복에서, 포인터를 서로 향해 이동시킨다. 이는 첫 번째 인덱스에서 시작한 포인터를 증가시키거나, 마지막 인덱스에서 시작한 포인터를 감소시키거나, 또는 둘 다 수행함을 의미한다. 어떤 포인터를 이동할지는 우리가 해결하려고 하는 문제에 따라 다르다.

다음은 이 개념을 설명하는 의사 코드이다:

function fn(arr):
    left = 0
    right = arr.length - 1

    while left < right:
        문제에 따라 여기에 일부 로직을 수행한다.
        다음 중 하나를 결정하기 위해 여기에 더 많은 로직을 수행한다:
            1. left++
            2. right--
            3. Both left++ and right--

이 기법의 장점은 포인터가 서로로부터 $n$ 거리에서 시작하여 매 반복마다 최소한 한 단계씩 가까워지기 때문에 while 루프에 대한 반복이 $O(n)$을 초과하지 않는다는 것이다. 따라서, 각 반복 내의 작업을 $O(1)$에 유지할 수 있다면, 최적의 성능을 내는 선형 시간 복잡도를 달성할 수 있다. 이제 이에 대한 몇 가지 예제를 통해 자세히 알아보도록 하자

---

예제 1: Palindrome

문자열 s가 주어졌을 때, 이 문자열이 회문이면 true를 반환하고, 그렇지 않으면 false를 반환해보자.

문자열이 회문일 경우, 그 문자열은 앞에서부터 읽으나 뒤에서부터 읽으나 동일하다. 이는 문자열을 뒤집어도 원 문자열이 유지되는 것을 의미한다. 예시로 “abcdcba”나 “racecar”가 있다.

문자열을 뒤집으면, 첫 번째 문자가 마지막 문자 위치에 오게 된다. 만약 문자열이 뒤집어진 상태에서도 동일하다면, 첫 문자와 마지막 문자가 동일하고, 두 번째 문자와 뒤에서 두 번째 문자가 동일하다는 것을 의미하며, 이 패턴이 계속 진행된다. 이를 확인하기 위해 투 포인터 기법이 사용될 수 있다. 처음에는 두 개의 포인터를 사용하여 문자열의 첫 문자와 마지막 문자를 검사한다. 다음 쌍의 문자를 검사하려면 포인터를 서로 한 칸씩 이동하면 된다. 포인터가 서로 만나거나 불일치하는 문자를 발견할 때까지 이 과정을 이어간다.

예제 1 상세 내용

우리는 두 개의 인덱스, 즉 왼쪽 인덱스와 오른쪽 인덱스를 추적한다. 처음에 왼쪽 인덱스는 첫 번째 문자를 가리키고, 오른쪽 인덱스는 마지막 문자를 가리킨다. 이 문자들이 서로 같지 않다면, 해당 문자열이 회문일 수 없다는 것을 알고, false를 반환한다.

그렇지 않으면 문자열이 회문일 수 있으므로, 다음 쌍을 확인해야 한다. 다음 쌍으로 넘어가기 위해, 왼쪽 인덱스를 하나 앞으로 이동시키고 오른쪽 인덱스를 하나 뒤로 이동시킨다. 다시, 문자 쌍이 같은지 확인하고, 같지 않다면 false를 반환한다.

우리는 불일치를 발견할 때까지(이 경우 문자열은 회문이 될 수 없으므로 false를 반환) 또는 포인터가 서로 만날 때까지(이는 모든 쌍을 확인하면서 문자열 전체를 검토했음을 나타냄) 이 과정을 계속한다. 모든 쌍을 불일치 없이 거치면 문자열이 회문임을 알 수 있으므로 true를 반환할 수 있다.

포인터가 서로 만날 때까지 알고리즘을 실행하려면 while 문을 사용할 수 있다. while 문의 각 반복은 하나의 쌍을 확인한다. 확인이 성공하면 left를 증가시키고 right를 감소시켜 다음 쌍으로 이동한다. 확인에 실패하면 false를 반환한다.

n은 전체 문자 수이므로, n - i - 1은 마지막, 마지막에서 두 번째, 마지막에서 세 번째 등의 문자에 해당한다. 입력값이 0으로 인덱싱되기 때문에 -1이 필요하다.

bool checkIfPalindrome(string s) {
    int left = 0;
    int right = s.size() - 1;
    
    while (left < right) {
        if (s[left] != s[right]) {
            return false;
        }
        left++;
        right--;
    }
    
    return true;
}

fn check_if_palindrome(s: &str) -> bool {
    let bytes = s.as_bytes();
    let mut left = 0;
    let mut right = s.len() - 1;

    while left < right {
        if bytes[left] != bytes[right] {
            return false;
        }
        left += 1;
        right -= 1;
    }

    true
}

문자 배열을 입력으로 사용하더라도, 현재의 알고리즘을 변경할 필요가 없다. 이는 투 포인터 기법이 추상적으로 반복 가능한 어떤 구조를 따라 인덱스 변수가 이동하기 때문에 가능하다.

이 방법은 굉장히 효율적이다. 왜냐하면 실행 시간은 $O(n)$이고, 사용하는 공간은 $O(1)$이기 때문이다. 입력 데이터의 크기와 상관없이 오직 두 정수 변수만을 사용하므로, 메모리 공간은 매우 절약된다. 알고리즘의 시간 복잡도는 $O(n)$인데, 그 이유는 while 문을 사용한 반복 각각이 $O(1)$의 시간을 소모하고, 이 while 문 반복은 $O(n)$을 초과할 수 없기 때문이다. 이 포인터들은 처음에 서로 $O(n)$의 거리에 떨어져 있으며, 반복할 때마다 한 단계씩 서로에게 가까워진다.

---

예제 2: 두 수의 합이 목표값인 쌍의 존재 여부

중복되지 않는 정수로 정렬된 배열과 목표 정수가 주어졌을 때, 두 수의 합이 목표값과 같은 수의 쌍이 존재하면 true를 반환하고, 그렇지 않으면 false를 반환해보자. 이 문제는 Two Sum과 유사하다. (Two Sum에서는 입력이 정렬되지 않는다).

예를 들어, nums = [1, 2, 4, 6, 8, 9, 14, 15] 및 target = 13이 주어진 경우, 4 + 9 = 13이므로 true를 반환한다.

가장 직관적인 해결 방법은 모든 숫자 쌍을 반복하여 확인하는 것이다. 이 방식은 각 숫자가 다른 숫자와 짝을 이루게 되므로 $O(n^2)$의 시간 복잡도를 가진다. 여기서 $n$은 배열의 길이이다. 배열이 정렬된 상태이므로, 투 포인터 기법을 사용하면 시간 복잡도를 $O(n)$으로 줄일 수 있다.

예제의 입력을 사용하여 이를 살펴보자. 투 포인터 기법을 사용하여, 첫 번째 숫자와 마지막 숫자부터 확인을 시작한다. 이들의 합계는 1 + 15 = 16이다. 16은 목표값보다 크므로, 합계를 줄이기 위해 오른쪽 포인터를 이동한다. 다음으로, 1 + 14 = 15의 합계를 얻게 되는데, 이 경우에도 합계가 더 크므로 오른쪽 포인터를 이동한다. 이후 1 + 9 = 10이 되며, 이 합계가 더 작으므로 왼쪽 포인터를 이동하여 합계를 증가시켜야 한다. 2 + 9 = 11은 목표값보다 작으므로 포인터를 다시 이동시킨다. 결국, 4 + 9 = 13으로 목표값에 도달한다.

이 알고리즘이 작동하는 원리는 다음과 같다: 숫자가 정렬되어 있기 때문에, 왼쪽 포인터를 이동하면 해당 포인터가 가리키는 값이 계속해서 증가한다(nums[left] = x). 반대로, 오른쪽 포인터를 이동하면 가리키는 값이 계속해서 감소한다(nums[right] = y). x + y > target인 상황에서는 x가 계속 증가할 수밖에 없으므로, y와의 조합으로는 해결책을 찾을 수 없다. 따라서 가능한 해결책이 있다면 y를 감소시키며 그것을 찾아야 한다. x + y < target인 경우에도 비슷한 논리가 x에 적용되어, x를 증가시키며 해결책을 찾아야 한다.

예제 2 상세 내용

nums = [3, 6, 21, 23, 25] 배열과 target = 27이 있다고 해보자. 우리의 목표는 두 수를 골라 그 합이 target이 되는 것이다. 투 포인터 기법을 사용하여, 배열의 처음과 끝에서 시작한다. 배열이 정렬되어 있으므로, 이것은 가장 작은 수와 가장 큰 수를 의미한다. 현재 3 + 25 = 28로, 이 합은 target보다 크다.

25를 살펴보면, 가장 작은 수와의 합산도 target을 초과하는 것을 알 수 있다. 이는 25가 답의 일부일 수 없다는 것을 의미한다. 왜냐하면 25보다 작은 다른 수와 짝을 지어도 합이 더 커지기 때문이다. 따라서, 25를 제외하고 다음으로 큰 수인 23으로 넘어간다.

이제, 3 + 23 = 26으로, 이 합은 target보다 작다. 우리는 이미 25를 답에서 제외했다. 이 상황에서 23이 가장 큰 수가 된다. 그럼에도 불구하고 3과의 합이 목표치에 미치지 못한다. 이는 3이 더 큰 수와 짝을 지어도 target에 도달하지 못할 것이라는 의미이므로, 3 역시 답의 조건에서 제외한다.

다음으로 6이 선택된다. 이제 합은 6 + 23 = 29가 되는데, 이는 또한 너무 크다. 이전의 논리에 따라, 23 역시 답이 될 수 없다는 결론을 내린다. 왜냐하면 가능한 가장 작은 수와의 합산도 target을 초과하기 때문이다. 그래서 이제 21로 넘어가 보면, 6 + 21 = 27이 되어 우리가 찾던 답을 얻게 된다.

이 알고리즘을 구현하기 위해, 포인터가 서로 만나거나, 합이 target과 같아질 때까지 포인터를 이동시키며 while 문을 실행한다. 만약 언제든지 합이 target과 같다면, 그때는 true를 반환한다. 포인터들이 서로 만났는데도 target을 찾지 못한 경우, false를 반환하면 된다. 이 방식은 입력된 배열을 처음부터 끝까지 체크하는 과정을 통해 이루어진다.

bool checkForTarget(vector<int>& nums, int target) {
    int left = 0;
    int right = nums.size() - 1;
    while (left < right) {
        int curr = nums[left] + nums[right];
        if (curr == target) {
            return true;
        }
        if (curr > target) {
            right--;
        } else {
            left++;
        }
    }

    return false;
}

fn check_for_target(nums: &[i32], target: i32) -> bool {
    let mut left = 0;
    let mut right = nums.len() - 1;
    
    while left < right {
        let curr = nums[left] + nums[right];
        if curr == target {
            return true;
        }
        if curr > target {
            right -= 1;
        } else {
            left += 1;
        }
    }

    false
}

이전 예제와 마찬가지로, 이 알고리즘은 $O(1)$의 공간 복잡도를 사용하며, 시간 복잡도는 $O(n)$이다.

---

투 포인터를 활용하는 또 다른 방법

포인터 두 개를 배열의 처음과 끝에서 시작하여 서로를 향해 이동시키는 방식은 투 포인터를 활용하는 여러 방법 중 하나에 불과하다. 알고리즘이 아름다운 이유 중 하나는 그것이 얼마나 추상적으로 다양한 방식으로 접근할 수 있는지에 있다. “투 포인터”는 단지 한 방법일 뿐, 여러 가지 형태로 구현될 수 있다. 다른 방법과 새로운 예제들을 통해 이 개념을 더 탐색해보자. 다음 설명하는 방법은 입력값으로 두 개의 순회 가능한 시퀀스(예: 두 배열)가 있는 경우에 적용할 수 있다.

두 입력 시퀀스를 동시에 순회하며 모든 요소를 확인한다.

이 개념을 단계별로 나누면 다음과 같다:

1. 각 순회 가능한 시퀀스마다 포인터 하나씩, 총 두 개의 포인터를 만든다. 이 포인터들은 첫 번째 인덱스에서 시작한다.
2. 포인터 중 하나가 해당 시퀀스의 끝에 도달할 때까지 while 문을 사용하여 반복한다.
3. 반복의 각 단계에서 포인터를 앞으로 이동시킨다. 이는 포인터 중 하나 혹은 둘 다를 증가시키는 것을 의미한다. 어떤 포인터를 이동시킬지는 우리가 해결하고자 하는 문제의 성격에 따라 달라진다.
4. while 문은 하나의 포인터가 끝에 도달하면 종료되므로, 반복이 끝났을 때 다른 포인터는 아직 해당 시퀀스의 끝에 도달하지 않을 수 있다. 경우에 따라 모든 요소를 체크해야 하기 때문에, 이 경우 두 시퀀스가 완전히 소진될 때까지 추가적인 코드를 작성해야 한다.

이러한 개념을 의사 코드로 나타내면 다음과 같다:

function fn(arr1, arr2):
    i = j = 0
    while i < arr1.length AND j < arr2.length:
        문제의 특성에 맞는 로직을 여기에 구현한다.
        그리고 다음 동작 중 하나를 결정하기 위한 추가 로직을 수행한다:
            1. i++
            2. j++
            3. i++ 및 j++

    // 4단계: 두 시퀀스가 모두 소진되었는지 확인한다.
    // 아래 루프 중 하나만 실행될 것이라는 점을 유의한다.
    while i < arr1.length:
        문제의 특성에 맞는 추가 로직을 여기에 구현한다.
        i++

    while j < arr2.length:
        문제의 특성에 맞는 추가 로직을 여기에 구현한다.
        j++

첫 번째 방법과 유사하게, 이 방법은 while 문 내의 작업이 $O(1)$이면 선형 시간 복잡도 $O(n + m)$을 가지게 된다. n은 arr1의 길이이고, m은 arr2의 길이이다. 이는 각 반복에서 적어도 하나의 포인터가 앞으로 이동하며, n + m 번의 이동 없이는 배열들이 완전히 소진되지 않기 때문이다. 이제 몇 가지 예제를 통해 이 방법을 더 깊이 이해해 보자.

---

예제 3: 두 배열의 정렬된 결합

정렬된 두 정수 배열 arr1과 arr2를 입력으로 받는다. 그리고 이들을 합쳐 정렬된 새 배열을 만들어 반환해보자.

이 문제를 해결하는 가장 단순한 방법은 두 배열을 합친 후, 정렬을 하는 것이다. 만약 n이 arr1과 arr2의 길이의 합이라면, 이 방식의 시간 복잡도는 정렬하는 데 드는 비용 때문에 $O(n \cdot \log{}n)$이 된다. 하지만, 입력 배열이 이미 정렬되어 있다면, 투 포인터 기법을 사용해 시간 복잡도를 $O(n)$까지 줄일 수 있다.

이전 설명에서는 n을 arr1의 길이로, m을 arr2의 길이로 정의했었다. 하지만 여기서는 n을 arr1의 길이와 arr2의 길이의 합으로 보고 있다. 이유는 무엇일까? 빅오 표기법에서는 변수를 우리가 필요에 따라 정의할 수 있다는 점을 기억하자. n과 m을 그대로 사용해도 되지만, 두 배열을 합치는 것을 고려할 때 전체 길이가 중요한 정보이므로 n으로 표현하는 것이 적절하다. 이에 따라 정렬 방식의 시간 복잡도는 $O((n + m) \cdot \log(n + m))$이고, 다음에 설명할 방식은 $O(n + m)$이 될 것이다.

정답 배열 ans를 만드는 과정은 단계적이다. 두 배열의 첫 번째 요소에서 시작하여, 각 단계에서 두 요소를 비교한다. 더 작은 값을 ans에 추가하고, 그에 해당하는 배열의 포인터를 다음 위치로 옮긴다. 이 과정을 반복하면, 최종적으로 정렬된 배열을 얻을 수 있다.

예제 3 상세 내용

배열의 길이가 $n$일 때, 정렬하는 데 필요한 시간은 $O(n \cdot \log{}n)$이다. 그러나 이미 정렬된 배열을 이용한다면, $\log{}n$ 요소를 줄일 수가 있어 시간 복잡도를 향상시킬 수 있다.

처음에는 각 배열에서 가장 작은 숫자를 보고 시작한다. 두 숫자 중 더 작은 숫자는 반드시 다른 숫자 앞에 와야 한다. 그래서 결과 배열에 더 작은 숫자를 추가하고, 그 배열에서 다음 숫자로 넘어간다. 만약 두 숫자가 같다면 어느 쪽을 선택해도 상관없다. 그저 선택하기 나름이다.

이 단계를 하나의 배열이 더 이상 남은 숫자가 없을 때까지 계속한다. 그 상황이 오면, 다른 하나의 배열에는 여전히 숫자들이 남아 있다. 이 요소들은 이미 비교를 마친 배열의 원소들보다 모두 큰 값이다. 그래서 이 남은 요소들을 결과 배열 뒤쪽에 그대로 추가하기만 하면 된다.

vector<int> combine(vector<int>& arr1, vector<int>& arr2) {
    vector<int> ans;
    int i = 0, j = 0;
    while (i < arr1.size() && j < arr2.size()) {
        if (arr1[i] < arr2[j]) {
            ans.push_back(arr1[i]);
            i++;
        } else {
            ans.push_back(arr2[j]);
            j++;
        }
    }
    
    while (i < arr1.size()) {
        ans.push_back(arr1[i]);
        i++;
    }
    
    while (j < arr2.size()) {
        ans.push_back(arr2[j]);
        j++;
    }
    
    return ans;
}

fn combine(arr1: Vec<i32>, arr2: Vec<i32>) -> Vec<i32> {
    let mut ans = Vec::new();
    let (mut i, mut j) = (0, 0);

    while i < arr1.len() && j < arr2.len() {
        if arr1[i] < arr2[j] {
            ans.push(arr1[i]);
            i += 1;
        } else {
            ans.push(arr2[j]);
            j += 1;
        }
    }

    while i < arr1.len() {
        ans.push(arr1[i]);
        i += 1;
    }

    while j < arr2.len() {
        ans.push(arr2[j]);
        j += 1;
    }

    ans
}

이전 두 예제와 마찬가지로, 이 알고리즘은 시간 복잡도가 $O(n)$이며, 공간 복잡도는 $O(1)$이다(출력을 추가 공간으로 계산하지 않는 경우).

---

예제 4: 서브 시퀀스 여부 판단

문제 링크

두 문자열 s와 t가 주어졌을 때, s가 t의 서브시퀀스인 경우 true를, 그렇지 않은 경우 false를 반환하라.

문자열의 서브시퀀스는 원본 문자열에서 일부(또는 전혀) 문자를 삭제하여 얻을 수 있는 문자 시퀀스로, 남아 있는 문자의 상대적 순서는 유지된다. 예를 들어, “ace”는 “abcde”의 서브시퀀스이지만 “aec”는 그렇지 않다.

이 문제에서는 s의 문자들이 t 내에 동일한 순서로 존재하는지 확인해야 하며, 문자 사이에 공백이 있어도 상관없다. 예를 들어 "ace"는 "abcde"의 서브시퀀스로 간주된다. 왜냐하면 "abcde" 내에 "a", "c", "e"가 순서대로 있기 때문이다. 문자들이 연속적이지 않아도 괜찮다는 점이 중요하다.

이 문제를 더 빠르게 해결하기 위해서, 투 포인터 기법을 적용할 수 있다. 만약 s[i]가 t[j]와 같다면, 이는 s의 i번째 문자를 t에서 발견했음을 의미한다. 따라서 i를 증가시켜 s의 다음 문자를 찾아볼 수 있다. 반복 과정에서 j는 상황에 상관없이 증가시켜야 한다는 점을 명심해야 한다(이 부분은 for 문을 사용하여 알고리즘에 적용할 수도 있다). 만약 s의 모든 문자를 t 내에서 찾을 수 있다면, 즉 알고리즘의 마지막에 i가 s의 길이와 같다면, s는 t의 서브시퀀스라고 할 수 있다.

예제 4 상세 설명

s의 모든 문자에 대해 t에서 일치하는 문자를 찾아야 한다. 예를 들어, s = "bc"이고 t = "abcd"라고 가정하자. 두 문자열의 첫 번째 문자부터 투 포인터 기법을 사용하여 비교를 시작한다. 우리의 목표는 s의 첫 문자 "b"를 찾는 것이다. 하지만 t의 첫 문자는 "a"이므로 일치하지 않는다. 그 결과, t에서 다음 문자로 넘어가야 한다. "b"를 아직 찾지 못했기 때문에 s는 그대로 둔다.

t의 다음 문자는 우리가 찾고 있는 "b"이므로 일치한다. 이제, s의 다음 문자인 "c"를 찾기 위해 넘어갈 수 있다. t에서 일치하는 문자는 한 번만 사용할 수 있기 때문에, t에서도 계속 전진해야 한다. t의 다음 문자 또한 "c"로, 우리는 또 다른 일치 항목을 발견한다. s의 모든 문자를 성공적으로 찾았기 때문에 s는 t의 서브시퀀스라고 할 수 있다.

이 과정을 통해 볼 수 있듯이, 문자가 일치하든 그렇지 않든, 우리는 계속해서 t 내에서 앞으로 나아간다. 문자가 일치할 경우, 해당 문자를 다시 사용할 수 없기 때문에 앞으로 나아가야 한다. 반면, 일치하지 않는 경우, 그 문자는 필요하지 않으므로 건너뛴다고 생각할 수 있다. s의 모든 문자와 일치하는 것을 목표로 하기 때문에, 일치하는 문자를 찾았을 때만 s에서 앞으로 나아간다.

bool isSubsequence(string s, string t) {
    int i = 0, j = 0;
    while (i < s.size() && j < t.size()) {
        if (s[i] == t[j]) {
            i++;
        }
        j++;
    }
    
    return i == s.size();
}

fn is_subsequence(s: String, t: String) -> bool {
    let (mut i, mut j) = 0;
    let s_chars: Vec<char> = s.chars().collect();
    let t_chars: Vec<char> = t.chars().collect();

    while i < s_chars.len() && j < t_chars.len() {
        if s_chars[i] == t_chars[j] {
            i += 1;
        }
        j += 1;
    }

    i == s_chars.len()
}

이 솔루션은 이전의 모든 예와 마찬가지로 $O(1)$ 공간을 사용한다. 시간 복잡도는 s와 t의 길이와 선형적이다.

---

마무리

여기서 소개된 방법들은 단순한 가이드라인에 불과하다. 예를 들어, 첫 번째 방법에서는 포인터를 첫 번째 및 마지막 인덱스에서 시작했지만, 경우에 따라 포인터를 다른 인덱스에서 시작하는 문제에 직면할 수도 있다. 두 번째 방법에서는 두 개의 포인터를 서로 다른 두 입력을 따라 전진시켰다. 가끔은 입력 배열/문자열이 하나뿐일 때도 두 개의 포인터를 첫 번째 인덱스에서 초기화하고 둘 다 전진시키는 경우가 있다.

투 포인터는 주로 두 개의 정수 변수를 사용하여 반복 가능한 요소들 사이를 이동하는 것을 의미한다. 이 글에서 다룬 전략들은 가장 흔한 패턴이지만, 문제에 다가설 때 항상 새로운 방법을 찾는 것이 중요하다. 심지어 “세 포인터”를 사용하는 문제들도 존재한다.

이 코스의 장과 글들은 이전 장에서 배운 개념들을 이후 장에 적용할 수 있도록 순서대로 구성되어 있다. 투 포인터는 이 글에서 다룬 것 이상으로 더 많은 활용 방안이 있으며, 이것이 투 포인터의 마지막 등장은 아니니 걱정하지 않아도 된다.

보너스 문제

• 344. Reverse String
• 977. Squares of a Sorted Array
• 557. Reverse Words in a String III
• 917. Reverse Only Letters
• 283. Move Zeroes
• 2000. Reverse Prefix of Word

---

출처: Leetcode