리트코드 - 58. Length of Last Word

리트코드 - 58. Length of Last Word

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

 

문제 설명

주어진 문자열 s는 단어와 공백으로 이루어져 있으며, 이 문자열에서 마지막 단어의 길이를 반환하세요.

단어란 공백이 없는 문자들로만 이루어진 최대 부분 문자열을 의미합니다.

 

의사코드

count = 0 반복문 시작 (s를 거꾸로 순회)     c = s를 한글자식 char로 변환     if (c == ' ')         if (count == 0)             continue         count 리턴      else          count++ 반복문 종료 count 리턴

 

풀이코드

1번 방법

class Solution {
    public int lengthOfLastWord(String s) {
        int count = 0;
        for (int i = s.length() - 1; i >= 0; i--) {
            char c = s.charAt(i);

            if (c == ' ') {
                if (count == 0) {
                    continue;
                } 
                return count;
            } else {
                count++;
            }
        }
        return count;
    }
}

2번 방법

class Solution {
    public int lengthOfLastWord(String s) {
        String[] words = s.split(" ");
        int last = words.length - 1;
        return words[last].length();
    }
}

 

코드설명

문자열을 char형으로 한글자씩 떼내어 결과를 확인하면 된다.

1번 방법은 직접 순회하는 방법이고 2번 방법은 배열을 만들어서 마지막 값을 확인하는 방법이다.

 

먼저 1번 방법은 문자열을 char형으로 바꿔 문자열의 끝에서부터 앞으로 순회를 시작한다.

' '가 아닌 경우 count를 하고, ' ' 인 경우에는 count를 리턴하며 종료하는데 여기서 문제는 문자열 제일 끝에 띄어쓰기가 나올 수 있다.

따라서 아무 문자열도 세지 않았을 때는 따로 count를 하지 않았을 것이고 count == 0 일때 continue를 하여 다음 순서로 넘어간다.

이렇게 하면 다음 ' ' 가 나왔을 때 count를 리턴할 것이다. 만약 끝까지 ' ' 가 나오지 않아도 반복문이 종료되므로 count를 리턴한다.

 

시간복잡도 - O(n)

공간복잡도 - O(1)

 

2번 방법은 string의 메소드인 split 을 이용해서 배열을 만들고, 마지막 배열의 길이를 출력하는 방법이다.

가독성 측면에서 좋은 코드고, 1번 방법보다는 시간이 더 걸리고 공간도 더 차지한다.

 

1번 방법에서는 마지막 문자열만 순회하면 메소드가 종료되지만,

2번 방법에서는 모든 문자열을 순회하여 배열로 만들고, 또 마지막 배열을 꺼내와야 하기 때문이다.

 

문자열이 극단적으로 많아진다면 2번 방법은 엄청난 시간이 걸릴 것이다.

 

시간복잡도 - O(n)

공간복잡도 - O(n)

 

문제를 풀며 생각한 흐름과 배운 점

간단한 문제라 빨리 풀었는데, 좀 더 빨리 풀고 싶다.

 

다른 코드

class Solution {
    public int lengthOfLastWord(String s) {
        int length = 0;
        int index = s.length() - 1;

        while (index >= 0 && s.charAt(index) == ' ') {
            index--; // 뒤쪽 공백 스킵
        }

        while (index >= 0 && s.charAt(index) != ' ') {
            length++;
            index--;
        }

        return length;
    }
}

for문을 사용하지 않고, while문을 사용하는 방법도 있다.

 

 

정리

문자열 자르기에 대한 빠른 접근 방법