[leetcode] 392. Is Subsequence

392. Is Subsequence

문제

https://leetcode.com/problems/is-subsequence/

string s와 string t가 문제에 주어지며 s가 t안에 속하는지 true or false로 답하는 문제이다.

여기서의 subsequence란, 오리지널 string에서 특정 문자들을 지웠을 때 나올 수 있는 string을 뜻한다.

(예: "ace"는 "abcde"의 subsequece)

풀이

이 문제는, string s에 있는 각 문자들이 string t에 있는지 하나씩 확인하고 지나가면 된다. 즉, s의 첫 문자를 t의 첫 문자부터 비교하여 동일한 문자가 나오면 s의 다음 문자를 t의 다음 문자(s와 동일했던 문자 다음)와 비교하는 식으로 풀면 된다.

나는 s의 문자들이 모두 t에 있는지 체크하는 용도로 count 변수를 사용했는데, 해당 변수를 사용하지 않고도 풀 수 있는 방법을 생각해보면 좋을 것 같다.

 

아래에 답안1과 답안2로 나누어 풀었는데, 이는 string을 다루는 방식의 차이이다. 오랜만에 C++을 보다보니.. string을 char로 변경해야만 iterator를 사용할 수 있다고 생각하고 푼 방식(답안1)까지 넣었다.

속도 차이는 별로 나지 않지만, 메모리를 고려하여 따로 vector로 바꾸지 않은 답안2를 추천한다.

답안1

#include <vector>
#include <string>
#include <iostream>

using namespace std;

class Solution {
public:
    bool isSubsequence(string s, string t) {
        vector<char> tChar(t.begin(), t.end());
        vector<char> sChar(s.begin(), s.end());
        auto tIter = tChar.begin();
        int subCount = 0;
        for(auto sIter = sChar.begin(); sIter != sChar.end(); sIter++) {
            while(tIter != tChar.end()) {
                if(*sIter == *tIter) {
                    tIter++;
                    sCount++;
                    break;
                }
                else {
                    tIter++;
                }
            }
        }
        if(subCount == sChar.size())
            return true;
        else return false; 
    }
};

답안2

#include <string>
#include <iostream>

using namespace std;

class Solution {
public:
    bool isSubsequence(string s, string t) {
        string::iterator tIter = t.begin();
        int subCount = 0;
        for(string::iterator sIter = s.begin(); sIter != s.end(); sIter++) {
            while(tIter != t.end()) {
                if(*sIter == *tIter) {
                    tIter++;
                    subCount++;
                    break;
                }
                else
                    tIter++;
            }
        }
        if(subCount == s.length()) return true;
        else return false;
    }
};

참고 사항

leetcode에서는 왠만한 std용 라이브러리를 포함한 채로 코드를 돌려주므로 따로 vector나 string을 include할 필요는 없지만, leetcode가 아닌 다른 곳에서 코드를 짤 경우를 대비하여 넣어 답안을 만들었다.