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

문제 링크

---

1. 아이디어

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

---

2. 복잡도

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

($N$ = my_string의 길이, $Q$ = queries의 길이)

---

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 s, int e) {
        while (s < e) {
            char tmp = arr[s];
            arr[s] = arr[e];
            arr[e] = tmp;
            s++;
            e--;
        }
    }
}

#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;
}

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

    return "".join(s)

---