[Leet Code] 2114. Maximum Number of Words Found in Sentences

문제 원본: https://leetcode.com/problems/maximum-number-of-words-found-in-sentences/

문제

sentence는 앞뒤에 공백들이 없는 단 하나의 공백으로 분리된 words의 리스트이다.
각 sentences[i]가 한 sentence를 나타내는 문자열 배열 sentences가 주어진다.
한 문장 내의 단어의 최대 개수를 반환하라.

Example 1:

Input: sentences = ["alice and bob love leetcode", "i think so too", "this is great thanks very much"]
Output: 6
Explanation: 
- The first sentence, "alice and bob love leetcode", has 5 words in total.
- The second sentence, "i think so too", has 4 words in total.
- The third sentence, "this is great thanks very much", has 6 words in total.
Thus, the maximum number of words in a single sentence comes from the third sentence, which has 6 words.

Example 2:

Input: sentences = ["please wait", "continue to fight", "continue to win"]
Output: 3
Explanation: It is possible that multiple sentences contain the same number of words. 
In this example, the second and third sentences (underlined) have the same number of words.

Constraints:

• 1 <= sentences.length <= 100
• 1 <= sentences[i].length <= 100
• sentences[i]는 소문자와 ‘ ‘으로만 이루어져 있다.
• sentences[i]는 앞뒤에 공백이 없다.
• sentences[i]의 모든 단어들은 하나의 공백으로 분리된다.

접근 방법

sentences를 반복문으로 순회하면서 한 문장씩 split()함수를 통해 공백을 기준으로 분리한다. split() 함수는 구분자를 기준으로 분리된 배열을 반환하니, 그 분리된 배열의 길이를 구하면 단어의 개수가 나올 것이다. 문장마다 해당 과정을 반복하면서, 단어 개수의 최대값을 구하고 이를 반환한다.

풀이

Java

class Solution {
    public int mostWordsFound(String[] sentences) {
        int maxWordsNum = 0;
        for (String sentence : sentences) {
            String[] split = sentence.split(" ");
            int wordsNum = split.length;
            
            if (wordsNum > maxWordsNum)
                maxWordsNum = wordsNum;
        }
        return maxWordsNum;
    }
}

• Runtime: 2ms
• Memory: 42MB

C#

Split() 사용

public class Solution {
    public int MostWordsFound(string[] sentences) {
        int maxWordsNum = 0;
        foreach (String sentence in sentences) {
            String[] split = sentence.Split(" ");
            int wordsNum = split.Length;
            
            if (wordsNum > maxWordsNum)
                maxWordsNum = wordsNum;
        }
        return maxWordsNum;
    }
}

• Runtime: 117ms
• Memory: 39.5MB

Split() 미사용

위의 방법이 제출자들 기준으로 55% 정도의 효율을 보여줘서, 상위권 유저들은 어떻게 했나 살펴봤다. 상위권 유저들은 Split() 함수를 쓰지 않았고, 문장에 공백이 있는지를 기준으로 단어의 개수를 셌다. 즉, 공백이 있으면 단어의 개수 = 공백의 개수 + 1인 것이다.

public class Solution {
    public int MostWordsFound(string[] sentences) {
        int maxWordsNum = 1;
        
        foreach (String sentence in sentences)
        {
            int wordsNum = 1;
            
            for (int i = 0; i < sentence.Length; i++)
            {
                if (sentence[i] == ' ')
                    wordsNum++;
            }
            if (wordsNum > maxWordsNum)
                maxWordsNum = wordsNum;
        }
        return maxWordsNum;
    }
}

• Runtime: 80ms
• Memory: 40.5MB

Python

class Solution:
    def mostWordsFound(self, sentences: List[str]) -> int:
        max_words_num = 1
        
        for sentence in sentences:
            words = sentence.split(" ")
            if len(words) > max_words_num:
                max_words_num = len(words)
        return max_words_num

• Runtime: 32ms
• Memory: 14MB 처음에는 len(words)를 max_words_num에 할당해서 썼는데, 그렇게 하니까 Runtime이 70ms가 나왔다. 혹시나 해서 max_words_num 대신에 len() 연산을 두 번 하게 했는데, 이게 더 빨랐다. 아마 변수가 메모리의 공간을 할당받는 시간도 Runtime에 큰 영향을 미치는 것 같다.