리트코드 - 392. Is Subsequence

리트코드 - 392. Is Subsequence

출처 - https://leetcode.com/problems/is-subsequence/description/?envType=study-plan-v2&envId=top-interview-150

 

문제 설명

주어진 두 개의 문자열 s와 t가 있을 때, s가 t의 부분 문자열(subsequence)인 경우 true를 반환하고, 그렇지 않은 경우 false를 반환합니다.

문자열의 부분 문자열은 원래 문자열에서 일부 문자를 삭제하더라도 남아있는 문자들의 상대적인 위치를 변경하지 않고 형성된 새로운 문자열을 의미합니다. 예를 들어, "ace"는 "abcde"의 부분 문자열입니다. 반면에 "aec"는 부분 문자열이 아닙니다.

 

의사코드

index = 0 if (s의 길이가 0이면)     true 리턴 반복문 시작 (t문자열 순회)     c1 = t 한글자씩 떼넴     c2 = s 한글자씩 떼넴     if (c1 == c2)         index++         if (index == s.length())             true 리턴 반복문 종료 false 리턴

 

풀이코드

class Solution {
    public boolean isSubsequence(String s, String t) {
        int index = 0;

        if (s.length() == 0) {
            return true;
        }

        for (int i = 0; i < t.length(); i++) {
            char c1 = t.charAt(i);
            char c2 = s.charAt(index);
            
            if (c1 == c2) {
                index++;

                if (index == s.length()) {
                    return true;
                }
            }
        }
        return false;
    }
}

코드설명

주어진 s 문자열을 한글자씩 떼서 인덱스 0부터 시작해서 t의 한글자씩 비교하여 같으면 다음 인덱스로 넘어간다.

만약 s의 마지막 인덱스까지 도달한다면 true를 리턴하고, 아니면 false를 리턴한다.

 

코드에서 주의할 것은 마지막 글자가 같을때에 index가 실제 인덱스를 벗어나는 s.length()의 크기가 된다 것이다.

예를 들어 "ab"라는 문자열이 있다면 a를 비교하여 같으면 index는 1이 되고, b를 비교하여 같으면 index가 2가 된다.

따라서 index == s.length() 로 조건을 걸어주어야 맞다.

 

시간복잡도 - O(n)

공간복잡도 - O(1)

 

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

그렇게 어렵지 않은 문제였다.

런타임은 1ms로 상위 퍼센트였는데 메모리 차이가 생각보다 끝부분에 있어서(22%) 리팩토링을 해봤다.

 

class Solution {
    public boolean isSubsequence(String s, String t) {
        int index = 0;
        int index2 = 0;

        if (s.length() == 0) {
            return true;
        }

        while (index < s.length() && index2 < t.length()) {
            if (s.charAt(index) == t.charAt(index2)) {
                index++;
                index2++;
            } else {
                index2++;
            }
        }

        if (index == s.length()) {
            return true;
        }
        return false;
    }
}

기본적인 원리는 동일한데 보기 좋은 방식으로 바뀌었다.

그렇지만 메모리가 여전히 27%로 낮다.

 

class Solution {
    public boolean isSubsequence(String s, String t) {
        int i = 0;
        int j = 0;

        if (s.length() == 0) {
            return true;
        }

        while (i < s.length() && j < t.length()) {
            if (s.charAt(i) == t.charAt(j)) {
                i++;
                j++;
            } else {
                j++;
            }
        }

        if (i == s.length()) {
            return true;
        }
        return false;
    }
}

인덱스 명칭을 i,j로 바꿨더니 0.5mb가 줄면서 85%로 올라갔다.

쉬운 문제에서는 이것까지 신경 안써도 될 것 같다.

 

정리

문자열 비교하기