[LeetCode][문자열] 344. Reverse String

문제 확인 하러 가기 : https://leetcode.com/problems/reverse-string/description/

1. 코드

class Solution {
    public void reverseString(char[] s) {
        // 입력 배열 s의 길이
        int len = s.length;

        // ex) len = 10인 경우,
        // 0 <-> 9
        // 1 <-> 8
        // 2 <-> 7
        // 3 <-> 6
        // 4 <-> 5
        // 번째 원소 끼리 서로 자리 교환
        for(int i=0; i<len/2; i++){
            char temp = s[i];
            s[i] = s[len-1-i];
            s[len-1-i] = temp;
        }
    }
}

2. 풀이

처음에 문제에 in-place 알고리즘으로 풀어야한다는 조건이 있어서 이게 무슨 소린가 했었다.

검색해보니

추가적인 메모리 공간을 많이 필요로 하지 않는 혹은 전혀 필요하지 않는 알고리즘
출처

이라고 하더라.

아무튼 이번 문제도 역시나 어렵지 않게 풀이법을 생각해냈다.

우선, 두 가지 풀이법이 생각이 났었는데,

첫 번째 방식,

맨 앞 칸에서 시작해서 자신보다 뒤에 있는 숫자와 계속 swap 하며 맨 끝으로 보낸다. 이 행위를 [문자열길이-1] 만큼 반복하면된다.

두 번째 방식,

양 끝 값끼리 서로 swap을 하고 양 쪽 모두 한 칸씩 안쪽으로 들어온다.

각 각 O(n*m), 2번은 O(n) 의 시간복잡도가 발생하기 때문에 본인은 두번째 방식 을 택했다.

알고리즘에 대해 좀 더 설명을 하자면,

마치 가우스 합 공식과 비슷하게

['h', 'e', 'l', 'l', 'o'] 가 있을때

'h' <-> 'o'
'e' <-> 'l'
를 서로 자리를 바꿔준다.

양끝을 서로 바꿔주기때문에 배열 길이의 절반 만큼 만 반복을 해주면된다.