[LeetCode] - 344. Reverse String

LeetCode는 프로그래밍 문제를 풀며 코딩 실력을 향상할 수 있는 온라인 플랫폼입니다. 다양한 알고리즘 및 데이터 구조 문제를 제공하며, 면접 대비에 유용합니다. 해당 문제는, LeetCode Problems에서 볼 수 있는 난이도 '쉬움 (Easy)' 단계인 "Reverse String" 문제입니다.

--> https://leetcode.com/problems/reverse-string/description/

 

문제 :

Write a function that reverses a string. The input string is given as an array of characters s. You must do this by modifying the input array in-place with O(1) extra memory.

---

Example 1 :

Input : s = ["h","e","l","l","o"]

Output : ["o","l","l","e","h"]

 

Example 2:

Input : s = ["H","a","n","n","a","h"]

Output : ["h","a","n","n","a","H"]

 

Constraints:

• 1 <= s.length <= 10^5
• s[i] is a printable ascii character.

---

이 문제는 주어진 문자 배열을 제자리에서 뒤집는 함수를 작성합니다. 추가 메모리를 사용하지 않고 O(1)의 공간 복잡도로 수행해야 합니다. 바로 제 코드를 보여드리겠습니다 : 

class Solution {
    public void reverseString(char[] s) {
        char[] s2 = new char[s.length];
        int i = s.length - 1;
        int j = 0;

        while (i >= 0) {
            s2[j] = s[i];
            i--;
            j++;
        }

         for (int k = 0; k < s.length; k++) {
            s[k] = s2[k];
        }

       
    }
}

 

 

• 추가 배열 초기화:
  • 주어진 배열 s와 같은 길이의 새로운 배열 s2를 생성합니다.
• 뒤집기 반복문:
  • i는 원래 배열 s의 끝에서 시작하고, j는 새로운 배열 s2의 시작에서 시작합니다.
  • i가 0보다 크거나 같은 동안 반복하며, s의 마지막 문자부터 s2의 첫 문자에 복사합니다.
  • 반복할 때마다 i는 감소하고 j는 증가합니다.
• 원래 배열에 복사:
  • 새로운 배열 s2의 값을 원래 배열 s에 복사합니다.
  • 배열의 모든 요소를 처음부터 끝까지 순회하며 복사합니다.

하지만, 코드를 쓰다 보니 제 문제점 하나를 발견했습니다. 그건 바로, 이 코드가 공간 복잡도가 O(n) 이라는 겁니다. 

 추가 배열 s2를 사용하기 때문이죠. 

 

이를 개선하고자, 다시 조금만 만져서 코드를 짜봤습니다 : 

class Solution {
    public void reverseString(char[] s) {
        int left = 0;
        int right = s.length - 1;
        while (left < right) {
            char temp = s[left];
            s[left] = s[right];
            s[right] = temp;
            left++;
            right--;
        }
    }
}

 

 

여기선 temp 변수를 활용합니다 temp란, temporary, 즉 오리지널 변수를 저장해 둘 일시적인 변수입니다. 상세하게 설명하자면, 

 

• 포인터 초기화:
  • left 포인터는 배열의 시작을 가리키고, right 포인터는 배열의 끝을 가리킵니다.
• 교환 반복문:
  • left가 right보다 작을 동안 문자를 교환합니다.
  • temp 변수를 사용하여 left 포인터와 right 포인터의 문자를 교환합니다.
  • 각 반복마다 left는 증가하고 right는 감소합니다.

코드들의 시간 복잡도는 둘 다 O(n) 입니다.

 

---

 

 

개선된 코드의 Runtime 결과