문제
풀이 1 (2025-08-12)
아이디어
s가 t의 subsequence인지 확인하는 문제다. s에 등장하는 문자 순서대로 t에 모두 등장하는지만 확인하면 된다. 투포인터를 이용해서 구현했다.
엣지 케이스인 둘 중 하나가 빈 문자열인 경우를 처리했다. s가 빈 문자열이면 항상 true를 반환하고, t가 빈 문자열이면 s가 빈 문자열이 아닌 이상 false를 반환한다.
코드
function isSubsequence(s: string, t: string): boolean {let sIdx = 0,tIdx = 0;if (s.length === 0) return true;if (t.length === 0) return false;while (sIdx < s.length && tIdx < t.length) {const sChar = s[sIdx];while (tIdx < t.length && t[tIdx] !== sChar) {tIdx++;}if (tIdx >= t.length) return false;tIdx++;sIdx++;}return sIdx === s.length;}
시간 / 공간 복잡도
- 시간 복잡도: O(n) — t의 길이 n에 대해 한 번 순회
- 공간 복잡도: O(1)
풀이 2 (2026-03-30)
아이디어
풀이 1과 동일한 방법으로 풀었는데 코드가 좀 더 간결해졌다. s의 각 문자에 대해서 t에서 등장하는 위치를 찾는 방식으로 구현했다.
for...of 루프를 이용해서 s의 각 문자를 순회하면서, t에서 해당 문자가 등장하는 위치를 찾는다. 만약 t의 끝까지 탐색했는데도 해당 문자가 등장하지 않으면 false를 반환한다. 모든 문자가 순서대로 등장하면 true를 반환한다.
코드
function isSubsequence(s: string, t: string): boolean {// s가 t의 subsequence인지를 확인해야 함.// s에 등장하는 문자 순서대로 t에 모두 등장하는지만 확인하면 된다.let tidx = 0;for (const c of s) {while (tidx < t.length && c !== t[tidx]) tidx++;if (tidx >= t.length) return false;tidx++;}return true;}
시간 / 공간 복잡도
- 시간 복잡도: O(n) — t의 길이 n에 대해 한 번 순회
- 공간 복잡도: O(1)
end