[LeetCode/Python] 58. Length of Last Word

다시 알고리즘 공부를 꾸준히 하기 위한 작심삼일 x 1년! 프로젝트를 시작했다. (작심삼일이라도 꾸준히 하자라는 마음가짐이다)

 

문제 링크:

https://leetcode.com/problems/length-of-last-word/description/?envType=study-plan-v2&envId=top-interview-150

 

Easy 난이도인 만큼, 특히 python으로서는 아주 풀기 쉬운 문제였다.

 

[내 풀이]

class Solution:
    def lengthOfLastWord(self, s: str) -> int:
        word_list = s.strip().split()
        return len(word_list[-1])

 

시간 복잡도

where n is the length of the input string

Stripping: O(n)

Splitting: O(n)

=> O(n)

 

 

[다른 풀이]

1.

strip()을 할 필요가 없다. 어차피 split() 하면서 whitespace는 자동으로 strip 되기 때문이다.

참고로 split() 함수의 default 구분자는 공백 문자다(space, tab, enter 등)

class Solution:
    def lengthOfLastWord(self, s: str) -> int:
        word_list = s.split()
        if word_list:
	        return len(word_list[-1])
        return 0

 

또한, 조건에서 s의 길이는 1 이상이라고는 했으나, ' ' 로만 이루어졌을 수도 있기 때문에 그런 경우를 위해 if문으로 word_list가 존재하는지 확인하는 조건문을 넣은 것 같다.

그러나, 그 밑에 조건에 [There will be at least one word in s] 라고 되어 있었기 때문에 사실상 조건문은 필요가 없긴 하다!

 

2.

빠른 코드로 솔루션에 소개되어 있는 코드다. 위의 코드는 가장 쉬운 코드이지만, 시간복잡도가 O(n)이므로 사실 시간효율적이진 않기 떄문이다.

class Solution(object):
    def lengthOfLastWord(self, s):
        """
        :type s: str
        :rtype: int
        """
        i = len(s) - 1 
        length = 0

        while i >= 0 and s[i] == " ":
            i -= 1

        while i >= 0 and s[i] != " ":
            length += 1
            i -= 1

        return length

직접 마지막 단어를 추출해내는 코드다. 문장의 맨 뒤에서 시작해서 white space인 글자는 건너띄게 하고,

english letter일 경우에만 length에 추가하는 코드다.

 

모든 문장을 trim하거나 split할 필요가 없어 당연히 1번의 코드보다 시간이 더 빠를 것이다!!! WOW!

음.. Easy문제는 빠르게 풀었을 경우, 더 효율적인 다른 코드가 있는지 생각해보는 시간을 가져야겠다.