[LeetCode] - 151. Reverse Words in a String

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

--> https://leetcode.com/problems/fizz-buzz/description/

 

문제 : 

Given an input string s, reverse the order of the words.

A word is defined as a sequence of non-space characters.

The words in s will be separated by at least one space.

Return a string of the words in reverse order concatenated by a single space.

 

Note that s may contain leading or trailing spaces or multiple spaces between two words.

The returned string should only have a single space separating the words.

Do not include any extra spaces.

---

Example 1 :

Input : s = "the sky is blue"

Output : "blue is sky the"

 

Example 2 :

Input : s = " hello world "

Output : "world hello"

Explanation : Your reversed string should not contain leading or trailing spaces.

 

Example 3 :

Input : s = "a good example"

Output : "example good a"

Explanation : You need to reduce multiple spaces between two words to a single space in the reversed string.

 

Constraints :

• 1 <= s.length <= 10^4
• s contains English letters (upper-case and lower-case), digits, and spaces ' '.
• There is at least one word in s.

 

Follow-up : If the string data type is mutable in your language, can you solve it in-place with O(1) extra space?

---

이번 문제는, 주어진 문자열 s의 단어 순서를 반대로 바꾸는 문제입니다. 단어는 공백이 아닌 문자들의 연속으로 정의되며, 단어들 사이에는 최소 하나 이상의 공백이 존재합니다. 반환되는 문자열은 각 단어가 하나의 공백으로만 구분되어야 하며, 앞뒤에 불필요한 공백이 없어야 합니다.

바로 제 코드를 보시겠습니다 : 

 

class Solution {
    public String reverseWords(String s) {
        List<String> words = new ArrayList<>();
        StringBuilder reversed = new StringBuilder();

        int start = 0;
        for (int i = 0; i <= s.length(); i++) {
            if (i == s.length() || s.charAt(i) == ' ') {
                if (start < i) {
                    words.add(s.substring(start, i));
                }
                start = i + 1;
            }
        }
        // 이러면 ["the", "sky", "is", "blue"] 프린트할거임. 이제부터 StringBuilder 써서 끝내자.
        for (int i = words.size() - 1; i >= 0; i--) { 
            reversed.append(words.get(i) + " ");
        }
        reversed.deleteCharAt(reversed.length() - 1); // remove the " " in excess

        return reversed.toString();
    }
}

 

코드를 설명드리겠습니다 : 

1. 함수 정의 및 초기화:
   • words: 단어들을 저장하기 위한 리스트입니다.
   • reversed: 최종 결과 문자열을 저장하기 위한 StringBuilder입니다.
2. 단어 추출:
   • start : 현재 단어의 시작 인덱스를 추적합니다.
   • for 반복문을 통해 문자열 s의 각 문자를 순회합니다.
   • if (i == s.length() || s.charAt(i) == ' ') : 현재 문자가 공백이거나 문자열의 끝인 경우, 단어를 추출합니다.
   • if (start < i) : 공백이 연속된 경우를 피하기 위해 사용됩니다.
   • words.add(s.substring(start, i)) : 단어를 리스트에 추가합니다.
   • start = i + 1 : 다음 단어의 시작 인덱스를 설정합니다.
3. 단어 역순으로 추가:
   • for (int i = words.size() - 1; i >= 0; i--) : 리스트를 역순으로 순회합니다.
   • reversed.append(words.get(i) + " ") : 단어를 StringBuilder에 추가하고, 각 단어 사이에 공백을 추가합니다.
   • reversed.deleteCharAt(reversed.length() - 1) : 마지막에 추가된 불필요한 공백을 제거합니다.
4. 끝.

요약하자면 : 

1. 문자열 s를 순회하며 단어를 추출하여 리스트에 저장합니다.
2. 리스트를 역순으로 순회하며 StringBuilder에 단어를 추가합니다.
3. 마지막에 추가된 불필요한 공백을 제거하고, 결과 문자열을 반환합니다.

시간 복잡도는 ? :

• 단어 추출과 역순으로 추가하는 과정 모두 O(n) 시간 복잡도를 가집니다.

---

내 코드의 Runtime 결과