[LeetCode#151] Reverse Words in a String

 

❐ Description

---

문제링크	https://leetcode.com/problems/reverse-words-in-a-string/description
난이도	Medium (골드5)

 

이번 문제는 어떤 방식으로 푸느냐에 따라 개인적으로 느끼는 난이도에 차이가 있는 문제 같다.

기본적으로 제공해주는 메서드(trim, replaceAll)를 사용하면 비교적 간단하게 해결할 수 있다.

하지만, 면접에서 기본 메소드를 사용하지 말고 위 문제를 해결하라고 하면 어떻게 해야할지

생각해봐야 한다.

 

 

 

 

 

❐ 문제 분석

---

문제를 요약하자면,

1. 문장을 거꾸로 뒤집어라.
2. 앞뒤에 공백이 와서는 안된다.
3. 문자 사이에 공백은 하나여야 한다.
4. 주어진 문자열의 길이 : `1 <= s.length <= 104`
5. 영어 대소문자, digits, 공백으로 이루어짐
6. 적어도 하나의 단어가 있음.

 

 

 

 

 

❐ 문제 풀이

---

1. 기본 메소드(trim, replaceAll) 사용

public class SolutionV1 {

    public String reverseWords(String s) {
        String preprocessed = preprocessingInput(s);

        char[] charArray = preprocessed.toCharArray();
        Deque<Character> dq = new LinkedList<>();

        StringBuilder sb = new StringBuilder();
        for (int i = charArray.length - 1; i >= 0; i--) {
            char target = charArray[i];
            if ((int) target == 32) {
                while (!dq.isEmpty()) {
                    sb.append(dq.pollFirst());
                }
                sb.append(' ');
            } else {
                dq.addFirst(target);
            }
        }

        while (!dq.isEmpty()) {
            sb.append(dq.pollFirst());
        }
        return sb.toString();
    }

    private String preprocessingInput(String input) {
        return input.trim()
                .replaceAll("\\s+", " ");
    }

    public static void main(String[] args) {
        String s = "  the  sky  is    blue  ";

        SolutionV1 solution = new SolutionV1();
        String answer = solution.reverseWords(s);
        System.out.println(answer);
    }

}

 

🧩 STEP 1 ⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯

우선 주어진 문자열의 white-space를 전처리해야 한다고 판단했다.

따라서 문자열 앞뒤에 있는 연속되는 white-space와, 중간에 위치한 연속되는 white-space를 제거해줬다.

private String preprocessingInput(String input) {
    return input.trim()
            .replaceAll("\\s+", " ");
}

 

 

🧩 STEP 2 ⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯

그 다음으로는 `char`를 담을 Deque를 선언해준다. Deque 용도는 아래와 같다.

• charArray를 역순회하며 dq에 char를 넣는다.
• 빈칸을 만나게 되면 dq를 비우면서, StringBuilder에 append해준다.
• 마지막으로 while-space를 append해준다. 

Deque<Character> dq = new LinkedList<>();

StringBuilder sb = new StringBuilder();
for (int i = charArray.length - 1; i >= 0; i--) {
    char target = charArray[i];
    if ((int) target == 32) {
        while (!dq.isEmpty()) {
            sb.append(dq.pollFirst());
        }
        sb.append(' ');
    } else {
        dq.addFirst(target);
    }
}

 

 

🧩 STEP 3 ⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯

마지막 단계에서는 dq가 가득찬 상태로 남기 때문에, dq를 비워준다.

while (!dq.isEmpty()) {
    sb.append(dq.pollFirst());
}
return sb.toString();

 

아래의 제한 조건이 추가된다면?
1. 추가적인 메모리 공간 사용 X
2. trim, replaceAll 사용 X

 

 

2. Two-pointer

두가지 제약 조건이 추가된다면, Two-Pointer를 사용한 풀이를 생각해볼 수 있다.

이번 풀이의 흐름은 아래와 같다.

1. 주어진 문자열의 charArray를 뒤집는다.
2. two-pointer를 통해서 각 단어를 뒤집는다.
   • pointer A : white-space를 건너뛴다.
   • pointer B : char를 건너뛴다.
3. 빈 칸을 정리해준다.(단어 사이사이 빈칸 하나만 허용)

 

🧩 STEP 1 ⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯

private void reverse(char[] arr, int start, int end) {
    while (start < end) {
        char temp = arr[start];
        arr[start++] = arr[end];
        arr[end--] = temp;
    }
}

위 메소드의 역할은 주어진 배열의 시작과 끝지점 까지만 순서를 역순으로 바꾸는 것이다.

 

 

🧩 STEP 2 ⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯

[Step 1]에서 얻은 뒤집혀진 배열에서 단어를 찾아야 한다. 해당 문제에서 단어란, 공백과 공백 사이에 있는

알파벳의 집합을 의미한다.

 

여기서 단어를 찾는 과정에서 two-pointer가 필요하다.

private void reverseWords(char[] arr, int arrLen) {
    int start = 0, end = 0;
    
    while (start < end) {
        // start : white-space를 건너뛴다.
        while (start < end || (start < arrLen && arr[start] == ' ')) start++;
        
        // end : char를 건너뛴다.
        while (end < start || (end < arrLen && arr[end] != ' ')) spaceCursor++;
        
        // start ~ (end - 1) 까지 단어 reverse
        reverse(arr, start, end - 1);
    }
}

 

 

🧩 STEP 3 ⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯

Step1~2를 수행하면 아래와 같은 배열이 주어질 것이다.

[ ,  , b, l, u, e,  ,  ,  ,  , i, s,  ,  , s, k, y,  ,  , t, h, e,  ,  ]

문제 요구사항에 충족하기 위해서는 `앞 뒤 공백`, `문자 사이 단일 공백` 조건을 맞춰줘야 한다.

 

여기서도 two-pointer가 사용된다.

private void cleanUpSpaces(char[] arr, int arrLen) {
    int start = 0; end = 0;
    
    while (end < arrLen) {
        // white-space를 건너뛴다.
        while (end < arrLen && arr[end] == ' ') end++;
        
        // char를 건너뛰면서, 앞 공백들을 채워나아가며, 커서를 앞으로 이동한다.
        while (end < arrLen && arr[end] != ' ') arr[start++] = arr[end++]
        
        // white-space를 건너뛴다.
        while (end < arrLen && arr[end] == ' ') end++;
        
        // 완성된 단어의 바로 뒤에 한개의 공백을 유지하고, start를 한 칸 앞으로 이동한다.
        if (end < arrLen) a[i++] = ' ';
    }
}

// while (end < arrLen && arr[end] == ' ') end++;
// strat = 0, end = 0;
[ ,  , b, l, u, e,  ,  ,  ,  , i, s,  ,  , s, k, y,  ,  , t, h, e,  ,  ]
 ↑
end

// strat = 0, end = 1;
[ ,  , b, l, u, e,  ,  ,  ,  , i, s,  ,  , s, k, y,  ,  , t, h, e,  ,  ]
    ↑
   end

// strat = 0, end = 2;
[ ,  , b, l, u, e,  ,  ,  ,  , i, s,  ,  , s, k, y,  ,  , t, h, e,  ,  ]
       ↑
      end


// while (end < arrLen && arr[end] != ' ') arr[start++] = arr[end++]
// strat = 0, end = 2;
[b,  , b, l, u, e,  ,  ,  ,  , i, s,  ,  , s, k, y,  ,  , t, h, e,  ,  ]
 ↑     ↑
 s     e

// strat = 1, end = 3;
[b, l, b, l, u, e,  ,  ,  ,  , i, s,  ,  , s, k, y,  ,  , t, h, e,  ,  ]
    ↑     ↑
    s     e

// strat = 2, end = 4;
[b, l, u, l, u, e,  ,  ,  ,  , i, s,  ,  , s, k, y,  ,  , t, h, e,  ,  ]
       ↑     ↑
       s     e

// strat = 3, end = 5;
[b, l, u, e, u, e,  ,  ,  ,  , i, s,  ,  , s, k, y,  ,  , t, h, e,  ,  ]
          ↑     ↑
          s     e


// while (end < arrLen && arr[end] == ' ') end++; 
// strat = 3, end = 10;
[b, l, u, e, u, e,  ,  ,  ,  , i, s,  ,  , s, k, y,  ,  , t, h, e,  ,  ]
          ↑                    ↑
          s                    e


// if (end < arrLen) a[i++] = ' ';
// strat = 4, end = 10;
[b, l, u, e,  , e,  ,  ,  ,  , i, s,  ,  , s, k, y,  ,  , t, h, e,  ,  ]
             ↑                 ↑
             s                 e

 

 

 

 

 

---