557. Reverse Words in a String III

https://leetcode.com/problems/reverse-words-in-a-string-iii/description/

문제

정답

1. 처음 풀이 (split + reverse)

class Solution {
    public String reverseWords(String s) {
       String[] arr = s.split(" ");
        StringBuilder answer = new StringBuilder();
        
       for(int i = 0; i < arr.length; i++) {
            StringBuilder sb = new StringBuilder(arr[i]);
            if(i == arr.length -1) {
                answer.append(sb.reverse());
                break;
            }
            answer.append(sb.reverse()).append(" ");
            
            // .trim() 사용 시 문자열 양끝의 공백 제거 가능
       } 

        return answer.toString();
    }
}

• 단어별로 문자열을 나눠서 배열에 저장한다.
• StringBuilder의 reverse() 메서드를 활용해 뒤집어주고 answer에 더해준다.

• 별도의 배열을 사용하긴 하지만, 시간 복잡도가 O(N)로 간단하고 괜찮은 풀이인듯!

=> 단어를 뒤집는다는 것에서 two pointers를 생각

2. 두번째 풀이 (two pointers)

class Solution {
    public String reverseWords(String s) {
       char[] arr = s.toCharArray();

        int lt = 0;
        for(int rt = 0; rt <= arr.length; rt++) {
            if(rt == arr.length || arr[rt] == ' ') {
               reverse(arr, lt, rt-1);
               lt = rt + 1;
            }
        }

        return new String(arr);
    }

    private void reverse(char[] arr, int lt, int rt) {
         while(lt < rt) {
                    char tmp = arr[lt];
                    arr[lt] = arr[rt];
                    arr[rt] = tmp;
                    rt--;
                    lt++;
                }
    }
}

• s를 char 배열로 만든 뒤, In-Place 정렬을 하는 방식
• char 배열을 쭉 순회하다가, 인덱스가 끝에 도달하거나, ' '일 때 reverse를 시작
  • 단어별로 뒤집어줘야하기 때문, rt - 1 일 때 맨 마지막 문자도 고려해야하므로
    rt <= arr.length;
  • rt의 경우 ' '보다 한 칸 앞이므로 -1
  • reverse 작업이 다 끝나면 ' ' 인덱스보다 한칸 앞부터 시작하므로 lt = rt + 1

• for문으로 문자 한번씩 방문 O(N) + while문으로 문자 바꾸면서 한번씩 더 방문 O(N)
  => O(N)의 시간복잡도
• 풀이가 조금 복잡하지만, 둘 다 익혀놓으면 좋을듯 함!