[leetCode - Java/Two Pointer] 344. Reverse String

1. 문제

---

• 문제는 비교적 쉬운 편이다. 주어진 char 배열 s를 거꾸로 뒤집으면 된다.

2. 의사 코드

---

    Stack<Character> stack = new Stack<>(); // list도 상관 없다

    for(int i=s.length-1; i>=0; i--) {
        스택에 char배열의 마지막부터 삽입
    }

    for(stack.size()만큼 반복) {
        입력받은 배열을 뒤집기 위해 stack에 반대로 저장된 요소를 다시 입력받은 char 배열의 0번째 인덱스부터 넣어준다
    }

3. 시도

---

    Stack<Character> stack = new Stack<>();

    for(int i=s.length-1; i>=0; i--) {
        stack.add(s[i]);
    }

    for(int i=0; i<stack.size(); i++) {
        s[i] = stack.get(i);
    }

쉽게 성공했다. 하지만 Stack을 새롭게 생성하여 char배열의 값을 n번만큼 실행하고 저장하기에 시/공간 복잡도는 O(n)이 예상되었다. 개선이 필요한 부분으로 이 알고리즘의 문제에도 O(1)의 공간복잡도를 요구한다. 따로 stack이나 list를 생성하여 값을 저장하지 않고, 입력받은 배열 s의 자리만 바꿔보면 될 것이라 예상된다.

4. 개선

---

아래의 코드는 투 포인터를 활용하여 수정한 결과로 속도나 메모리 부분에서 확실히 개선된 것을 확인할 수 있으며 투 포인터는 아래와 같은 경우에 사용될 수 있다.

• 주로 배열이나 리스트 같은 선형 데이터 구조에서 사용
• 두 개의 포인터를 동시에 움직여가며 문제를 해결
• 한 쌍의 값이나 조건을 충족시키는 무언가를 찾는 문제

left와 right를 설정하여 하나씩 범위를 좁혀가는 방식이다.

    int left = 0;
    int right = s.length-1;

    while(left < right) {
        char temp = s[left];

        s[left] = s[right];
        s[right] = temp;

        left++;
        right--;
    }