151. Reverse Words in a String

[문제]

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.

 

[TC]

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 <= 104
• 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?

 

[접근]

앞 문제 풀이인 345. Reverse Vowels of a String 

풀이 중 하나를 활용하면 좋겠다고 생각했고, stack의 LIFO 성질과 StringBuilder가 바로 떠올라서 적용해보았더니, Accepted 가 나왔다.

 

[코드] C#

using System;

public class Solution {
    public string ReverseWords(string s) {
        
        Stack<string> st = new Stack<string>();
        StringBuilder sb = new StringBuilder();

        foreach (var chr in s)
        {
            if (chr == ' ' && sb.Length == 0) continue;

            if (chr == ' ' && sb.Length != 0)
            {
                st.Push(sb.ToString());
                sb.Clear();
                continue;
            }

            sb.Append(chr);
        }

        if(string.IsNullOrWhiteSpace(sb.ToString()) == false)
            st.Push(sb.ToString());
        sb.Clear();

        int count = 0;
        foreach(var elem in st)
        {
            string s1 = elem;
            foreach (var s2 in s1)
            {
                sb.Append(s2);
            }

            if(count < st.Count-1)
                sb.Append(" ");

            ++count;
        }

        return sb.ToString();
    }
}

 

[결과]

[후기]

이전 문제 풀이에서 Stack 풀이법이 나한테는 강하게 와닿았던듯하다. 쉬는시간에 짬내서 풀었는데, 문제를 이해하자마자 stack 과 stringbuilder를 활용하는 방안이 떠올랐다.

 

중간 실수 때문에 vs 컴파일러의 도움을 받았지만, 더욱 꼼꼼하게해서 두뇌디버깅으로 끝낼 수 있도록 연습해야겠다.