Leetcode - 151. Reverse Words in a String

문제

string s에 어떤 문장이 담겨있다. 이 문장의 단어의 순서를 뒤집어서 출력하라. 그리고 불필요한 while space는 제거하라.

Input: s = "the sky is blue"
Output: "blue is sky the"

Input: s = "  hello world  "
Output: "world hello"

아디이어

이런 종류의 문제는 최대한 인덱스를 직접 제어하지 않도록 코드를 작성해야한다는 사실을 이제야 깨달음. 배열이나 문자열의 인덱스를 2개이상 제어하다보면 논리적으로 코드를 읽기도 어려워지고 버그가 많아진다. c++로 작성한 아래 풀이1도 그나마 인덱스 i만 사용해서 괜찮긴하다. 하지만 scala 로 작성한 풀이2에서 fp스타일의 코딩은 이런의미에서 정말 은혜롭다.

• 풀이 1
  토큰을 나눠서 stack에 저장한뒤, pop하면서 합치기.

• 풀이 2
  문자열 전체를 reverse, 그리고 토큰으로 나눈뒤, 각 word를 reverse, 그리고 문자열로 합치기.

풀이 1

class Solution {
public:
    string reverseWords(string s) {
        stack<string> words;
        string sub = "";
        for (int i = 0; i < s.length(); i++) {
            if (s[i] == ' ') {
                if (sub.length() > 0) {
                    words.push(sub);
                    sub = "";
                }
            } else {
                sub += s[i];
            }
        }
        if (sub.length() > 0)
            words.push(sub);
        
        string ret = "";
        while (words.size() > 1) {
            ret += words.top() + " ";
            words.pop();
        }
        ret += words.top();
        return ret;
    }
};

풀이 2 (by Scala)

scala로 FP스타일로 풀이 (그러나 Runtime: 580 ms / Memory Usage: 55.1 MB)

object Solution {
    def reverseWords(s: String): String = {
        s.reverse
            .split(" ")
            .filter(x => x.size > 0)
            .map(x => x.reverse)
            .mkString(" ")
    }
}

풀이 2 (by Rust)

동일 로직을 Rust로. Rust는 iterator의 consumer개념(collect())이 있어서 사용성은 조금 더 복잡함. 그런데, Scala와 다르게 수행 속도와 메모리 측면에서 너무 성능이 뛰어남 ㄷㄷ
(Runtime: 1 ms, Memory Usage: 2.3 MB)

Rust를 사용하면 함수형 스타일의 코딩을 할 수 있으면서 성능도 잡을 수 있음 ㄷㄷ

impl Solution {
    pub fn reverse_words(s: String) -> String {
        s.chars().rev().collect::<String>()
            .split(" ")
            .filter(|x| x.len() > 0)
            .map(|x| x.chars().rev().collect::<String>())
            .collect::<Vec<String>>()
            .join(" ")
    }
}