[Programmers] #181913 - 문자열 여러 번 뒤집기 [Java][C++][Python]

문제 링크

---

1. 아이디어

queries에 담긴 [s, e] 구간들을 순서대로 하나씩 뒤집어 나가면 되는 문제다. 각 쿼리마다 s와 e를 양 끝에서 좁혀오는 투 포인터로 두 문자를 맞바꾸면 해당 구간이 뒤집히고, 이를 쿼리 개수만큼 반복하면 최종 문자열이 완성된다.

---

2. 복잡도

접근	시간	공간
풀이	$O(N \times Q)$	$O(N)$

($N$ = my_string의 길이, $Q$ = queries의 길이. C++는 인자로 받은 my_string을 제자리에서 뒤집어 반환해 공간 $O(1)$)

---

3. 코드

풀이 [Java][C++][Python]

class Solution {
    public String solution(String my_string, int[][] queries) {
        char[] arr = my_string.toCharArray();
        for (int[] q : queries) {
            reverse(arr, q[0], q[1]);
        }

        return new String(arr);
    }

    static void reverse(char[] arr, int l, int r) {
        while (l < r) {
            char tmp = arr[l];
            arr[l] = arr[r];
            arr[r] = tmp;
            l++;
            r--;
        }
    }
}

#include <bits/stdc++.h>
using namespace std;

string solution(string my_string, vector<vector<int>> queries) {
    for (auto& q : queries) {
        reverse(my_string.begin() + q[0], my_string.begin() + q[1] + 1);
    }

    return my_string;
}

std::reverse를 활용해 간단하게 뒤집기를 했다. std::reverse는 반열린 구간 [first, last)를 받으므로, 닫힌 구간 [s, e]를 뒤집으려면 끝 반복자를 begin() + e + 1로 한 칸 넘겨 줘야 한다.

def solution(my_string, queries):
    s = list(my_string)
    for l, r in queries:
        s[l : r + 1] = s[l : r + 1][::-1]

    return "".join(s)

슬라이스 s[l : r + 1]로 뒤집을 구간을 떼어 [::-1]로 뒤집은 뒤 같은 구간에 다시 대입했다. 슬라이스 끝 인덱스가 열린 구간이라 r + 1을 써야 한다.

---