[코딩연습] Length of Last Word 마지막 단어의 길이 구하기

LeetCode 문제 중 난이도 Easy인 Length of Last Word이다. 문제 링크는 포스팅의 맨 마지막에 추가하였다. 언어는 Java를 사용했다.

  문제해석

알파벳 대/소문자 그리고 공백문자로 이루어진 String s에서 마지막 단어의 길이를 구하여라.

마지막단어가 존재하지 않으면 0을 리턴한다. 단어의 정의는 공백없이 이루어진 문자열을 말한다.

Example : "Hello World"가 Input이라면 World의 글자수인 5 출력

간단한 경우부터 생각해보자.

문자열을 뒤에서부터 읽다가 s.charAt(i)에서 공백문자를 발견하면 전체 문자열의 길이에서 i+1을 빼서 공백 뒤의 문자의 개수를 구한다. 만약에 공백이 아예 존재하지 않아 for문이 끝날때까지 리턴이 발생하지 않는다면 하나의 단어로 이루어진 문자열이므로 그냥 문자열의 길이를 반환하면 된다.

class Solution {
    public int lengthOfLastWord(String s) {
 
        for(int i=s.length()-1 ; i>=0 ; i--){
            if(s.charAt(i)==' '){
                return s.length()-i-1;
            }
        }        
        return s.length();
    }
}

* charAt(int index)는 문자열에서 해당 인덱스의 문자를 반환한다. 인덱스는 0부터 시작한다.

만약 문자열의 마지막 문자가 공백문자라면 어떨까? 위의 코드대로라면 "I am a Genius   "의 반환값은 0이 된다. 우리가 얻어야 할 값은 6이다. 이 문제를 해결하기 위해 공백문자를 만났을 경우 그 뒤에 알파벳이 있었는지 확인하고 나서 리턴을 하도록 코드를 바꿔 보자.

"I am a Genius   "라는 문자열을 알파벳을 만나기 전까지 거꾸로 읽다가 s를 만나면 hasChar를 true로 바꾼 뒤 알파벳의 개수가 늘어날 때마다 count를 늘려 준다. 그러다가 또 다시 공백문자를 만나면 그 때 count 값을 반환한다.

class Solution {
    public int lengthOfLastWord(String s) {
        int count=0;
        
        //알파벳이 있었는지 확인하기위한 값
        boolean hasChar=false;
        
        //뒤에서부터 세서 알파벳이 나오고 또 공백문자 나오면 count리턴
        for(int i=s.length()-1 ; i>=0 ; i--){
            if(s.charAt(i)!=' '){
                hasChar=true;
                count++;
            }else{
                if(hasChar){
                    return count;
                }
            }
        }
        
        return count;
    }
}

for문 내에서 리턴이 발생하는 경우는 hasChar가 true인 상태에서 공백문자를 만났을 때이다. 문자열의 맨 앞까지 전부 읽었는데도 리턴이 발생하지 앖는 경우는 두가지이다. 문자열 전체가 공백문자로 이루어졌거나, 문자열 전체가 한 단어 여서 공백문자가 없을 때이다. 그럴 때는 count를 리턴하면 된다. 전자라면 count가 처음에 선언한 그대로 0일 것이고 후자라면 count가 문자열의 길이와 같게 된다.

Worst Case는 문자열 전체가 공백이거나, 공백이 없는 문자열일 경우 전체 문자열을 읽어야 하므로 시간복잡도는 O(n)이고 추가적인 공간을 사용하지 않으므로 공간복잡도는 O(1)이다.

2019/02/25 - [프로그래밍문제풀기] - 빅오표기법(Big O notation)

다른 해결법도 있다. 문자열을 split()함수를 이용하여 공백문자를 기준으로 잘라 배열에 넣고 배열의 마지막 요소의 길이를 구하면 된다. 전체가 하나의 문자열이거나 전부 공백문자로 이루어진 경우에 대한 예외처리를 해 준다.

class Solution {
    public int lengthOfLastWord(String s) {
 
        //공백문자열이 없다면 전체 문자열의 길이를 반환
        if (!s.contains(" ")) return s.length();
        
        String [] ss = s.split(" ");
 
        //공백문자로만 이루어져있다면 0 반환
        if (ss.length == 0) return 0;
        
        //마지막 문자열의 길이 반환
        return ss[ss.length-1].length();
    }
}

두번째 방법은 코드 단 4줄로 구현이 가능하다! 대신 새로운 배열을 위한 추가적인 메모리를 필요로 하므로 공간복잡도가 O(n)으로 늘어나게 된다.

문제 출처 링크 - https://leetcode.com/problems/length-of-last-word