[2024] day 93. Leetcode 58. Length of Last Word

2024년부터 새롭게 다시 시작하는 코딩테스트

2024년 4월 1일 (월)
Leetcode daily problem

58. Length of Last Word

https://leetcode.com/problems/length-of-last-word/?envType=daily-question&envId=2024-04-01

Problem

문자와 공백으로 구성된 문자열 s가 주어질 때, 가장 마지막 문자의 길이를 반환한다. 여기서 문자는 공백을 포함하지 않고 오직 문자열로만 구성되어 있는 하위 문자열이다.

예를 들어 s = "Hello World" 이면,
공백을 제외한 World가 마지막 문자열로 World의 길이인 5를 반환하는 것이다.

Solution

string

주어진 문자열을 공백을 기준으로 분할하여 리스트에 저장하고, 해당 리스트를 탐색하면서 공백이 아닌 문자열만 새롭게 저장한다. 새롭게 저장한 배열의 마지막 문자열의 길이를 반환하는 방식으로 해결한다.

Code

class Solution:
    def lengthOfLastWord(self, s: str) -> int:
        sList = s.split(' ')
        sList = [string for string in sList if not string == '']
        return len(sList[-1])

Complexicity

시간 복잡도

주어진 입력 문자열 s를 공백으로 분할하고 리스트에 저장하고, 비어 있지 않는 문자열만 남겨서 마지막 길이를 반환하는 필터링 과정에서 입력 문자열 s의 길이에 비례하므로 시간 복잡도는 O(n) 이다.

공간 복잡도

입력 문자열을 분할한 후 필터링된 문자열들을 저장하기 위해 새로운 리스트가 사용되는데, 이 리스트의 크기는 입력 문자열에 있는 단어의 수에 비례하므로 공간복잡도는 O(n)이다.

---

굳이 리스트를 이용하지 않고 주어진 문자열의 공백을 제거하고 strip()을 이용해서 공백없이 문자열만을 분할할 수 있다. 분할한 문자열읠 배열의 마지막 문자의 길이를 반환하는 아래와 같이 단순하게 해결하는 편이 더 좋아보인다.

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

해당 코드의 시간복잡도는 입력 문자열을 strip() 메서드로 양쪽 공백을 제거하고 spilt() 메서드로 공백을 기준으로 문자열을 분할하는 과정에서 문자열 길이에 비례하는 O(n)이 소요된다.
또한 공백을 제거하고 문자열을 분할해서 해당 배열을 할당할 때 문자열의 길이에 비례하므로 공간복잡도 또한 O(n)이다.

그 외에 공간복잡도 O(1), 시간복잡도 O(n)으로 푸는 다른 방법도 있다.
문자열을 뒤에서부터 탐색하면서 length를 파악하는 것이다.

class Solution:
def lengthOfLastWord(self, s:str)->int:
	length = 0
    idx = len(s)-1
    
    while idx>=0 and s[idx] == ' ':
    	idx -=1
        
    while idx>=0 and s[idx] != ' ':
    	length+=1
        idx -=1
        
    return length