[Leetcode][C++][난이도 Easy] Length of Last Word

오늘 살펴볼 leetcode 문제는 난이도 easy 문제 중 하나인 Length of Last Word 문제입니다. Length of Last Word 문제는 주어진 문자열에서 띄어쓰기 문자 space를 기준으로 제일 마지막 단어의 길이를 반환하면 해결할 수 있는데요, space에 대한 약간의 예외처리만 적용해주면, 쉽게 해결할 수 있는 문제입니다. 먼저 문제에 대해 자세히 살펴보고, 제가 작성한 코드와 추천을 많이 받은 분의 솔루션 코드를 함께 살펴보겠습니다.

 

 

Length of Last Word 문제 분석

앞에서도 언급했던 것처럼, Length of Last Word 문제는 주어진 문자열 중 space 기준으로 제일 마지막에 있는 단어의 길이를 반환하면 해결합니다. 이 문제에서 단어의 정의를 space가 아닌 문자들로 구성된 maximal substring으로 보고 있씁니다. 또한, 문제에서 제약 조건도 문자열은 오직 영문자와 space로만 한정되어 있다고 하니, 영문자와 space만 고려해서 코드를 작성하면 됩니다. 이제 예제를 살펴보겠습니다.

 

 

 

 

 

 

 

첫번째 예제에서는 "Hello World"가 문자열로 주어졌습니다. 여기서 마지막 단어는 World 라는 것을 바로 알 수 있습니다. 따라서, World의 길이는 5이므로, 정답은 5가 됩니다. 그 다음 예제는 "   fly me   to   the moon  "이 문자열로 주어졌습니다. 이 문제를 통해서 space에 대한 에외처리를 해줘야 한다는 것을 알 수 있습니다. 왜냐하면, 마지막 단어인 moon 뒤에 space가 존재하고 있고, 작성된 코드가 항상 마지막 space 뒤에 등장하는 단어의 길이를 반환하도록 작성되어 있다면, 오류가 발생할 수 있기 때문입니다. 정답은 물론 moon의 길이인 4가 됩니다. 세번째 예제에서는 "luffy is still joyboy"라는 문자열이며, 마지막 단어가 joyboy이기 때문에, 정답이 6인 것을 알 수 있습니다.

 

<사진 1> Length of Last Word 문제

 

Length of Last Word 문제 해결을 위한 C++ 코드 

이제 제가 작성한 C++ 코드를 살펴보겠습니다. 우선 입력받은 문자열 s가 아무런 정보도 저장되어 있지 않은 빈 문자열인지를 검사합니다. 만약 빈 문자열이라면 단어도 존재하지 않는다는 의미이므로 0을 반환합니다.

 

 

 

 

 

 

 

문자열 s가 빈 문자열이 아니라면, 문자열의 맨 뒤의 문자부터 맨 앞의 문자까지 역행해서 for loop을 수행했습니다. 이렇게 작성하면, 맨 앞의 문자부터 탐색해야 하는 시간을 줄일 수 있다고 생각했습니다. for loop을 수행할 때는 문자열 내 현재 위치에 있는 문자가 space인지 아닌지를 검사한 후, space가 아니라면 최종 단어의 길이 정보인 result 변수의 값을 1씩 증가시킵니다. 만약 space이고, 이전에 result값이 갱신되었다면, for loop을 중단하고 result를 반환하면 됩니다.

 

class Solution {
public:
    int lengthOfLastWord(string s) {
        if (s.empty())
            return 0;
        
        int flag = 0;
        int result = 0;
        for (int i = s.length() - 1; i >= 0; i--)
        {
            if (s[i] != ' ')
            {
                result++;
                flag = 1;
            }
            else if (s[i] == ' ' && flag == 1)
                break;
        }
        
        return result;
    }
};

 

Length of Last Word 문제의 솔루션 코드 중 제일 많은 추천을 받은 코드

그러면 leetcode에서 이 문제의 솔루션으로 제일 많은 추천을 받은 코드도 살펴보겠습니다. 코드 안에 출처도 함께 기재해두었으니, 참고하셔도 좋습니다. 

 

 

이 코드에서는 문자열의 맨 끝의 인덱스를 tail 변수로 지정하고 while loop을 2번 수행합니다. 첫 번째 while loop에서는 현재 tail이 가리키는 문자가 space라면, tail을 1씩 줄여나갑니다. 이건 방금 전 두 번째 예제에 대한 예외 처리라고 볼 수 있습니다. 이후, 두 번째 while loop에서 space가 아닌 경우에 대해 반환하려는 값을 저장하는 len 변수의 값을 1씩 증가시키고, len을 반환합니다.

 

// 출처: https://leetcode.com/problems/length-of-last-word/solutions/21892/7-lines-4ms-c-solution/?orderBy=most_votes&languageTags=cpp

class Solution {
public:
    int lengthOfLastWord(string s) { 
        int len = 0, tail = s.length() - 1;
        while (tail >= 0 && s[tail] == ' ') tail--;
        while (tail >= 0 && s[tail] != ' ') {
            len++;
            tail--;
        }
        return len;
    }
};

 

지금까지 Length of Last Word 문제, 제가 작성한 C++ 코드, 추천을 제일 많이 받은 솔루션 코드를 전부 살펴보았습니다. 이번 문제를 통해서 문자열 처리 과정에서 예외처리를 꼭 염두해두고 코드를 작성해야 한다는 것을 알게되었습니다. 다음 leetcode 문제도 easy 난이도 문제 중 하나로 다시 찾아뵙겠습니다 ^^