LeetCode 344(Reverse String, java)

0. 문제

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

Reverse String - LeetCode

 

 

1. 문제 설명

- 문제에서 문자형 배열(char[] s)가 주어진다.

- O(1)의 시간 복잡도를 가지는 추가 메모리만을 사용하여 s를 역순으로 정렬하는 것이 문제의 핵심이다.

- 여기서 O(1)의 시간 복잡도를 가지는 추가 메모리가 의미하는 것은 기본 자료형을 사용하는 변수를 의미한다.

- 즉, 변수만을 사용하여 배열을 역순으로 정렬하라는 의미다.

 

 

2. 문제 해설

a) 첫 번째 접근

- 변수만을 사용하여 배열을 역순으로 정렬하는 방식은 꽤나 간단하다.

- 배열의 첫 번째 요소(start)와 마지막 요소(end)를 가리키는 two pointers 방식을 사용하면 되기 때문이다.

- while문을 사용하여 start < end일 때까지 배열의 요소를 swap 한다.

- 다음 코드를 보면서 이해해보자.

 

 

3. 정답 코드

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