💬 문제
문자열 s의 부분 문자열 중
중복 문자가 없는 가장 긴 것의 길이 반환
✍️ 나의 풀이
/**
* @param {string} s
* @return {number}
*/
var lengthOfLongestSubstring = function(s) {
let sub = '';
let res = 0;
for (let i = 0; i < s.length; i++) {
let idx = sub.indexOf(s[i]);
if (idx === -1)
sub += s[i];
else {
res = sub.length > res ? sub.length : res;
sub = sub.slice(idx + 1);
i--;
}
}
return Math.max(res, sub.length);
};res는 가장 긴 문자열의 길이를 저장하는 용도
문자열 s를 순회하면서 문자가 중복되지 않을 때까지
sub에 하나씩 저장하고, 중복되는 것이 발견되면
일단 길이 비교해서 res 값 바꾼 후
중복되는 문자의 위치까지 잘라낸 다음 다시 반복
마지막 문자까지 넣는 것에 성공했을 때 res 값 비교를 못하므로
반환할 때 현재 sub 길이와 비교해서 더 큰 값 반환
📌 결과
Accepted
Runtime 75ms (Beats 85.94%)
Memory 54.81MB (Beats 46.04%)
📚 러닝 포인트
어제 풀었던 문제와 매우 유사했기 때문에 어렵지 않게 해결할 수 있었다. 순회하는 방법도 이제 요령을 조금 깨달은듯? 메모리 효율이 조금 아쉬워서 다른 사람들 코드를 둘러봤는데 나처럼 문자열을 그대로 사용하기 보다 배열, set, map 등을 많이 활용해서 풀었더라. 특히 set이 중복 불가인데다가 일단 추가한 순서를 유지하기 때문에 제일 괜찮다고 생각했다.
그리고 어제 아무 생각 없이 포스팅 하고 나서 깨달았는데, 이 문제의 챕터 이름이 sliding window였다. 무엇인지 검색해보니까 알고리즘의 한 종류더라(!) 그리고 이전까지 쭉 했던 two pointers도 알고리즘 이름이었다... 그래서 이번 포스팅에서 한 번 짚고 넘어가보려고 한다.
우선 sliding window와 two pointers 알고리즘은 모두 1차원 배열을 2회 이상 반복 탐색해야 할 때 O(n^2)에서 O(n)으로 시간 복잡도를 줄일 수 있도록 부분 배열을 활용하는 방법이다. 둘의 차이점은 sliding window는 부분 배열이 고정적인 길이를 가지고 일정하게 움직이고, two pointers는 양쪽을 가리키는 변수가 존재해서 부분 배열 길이가 유동적이라는 점이다.
지금까지 문제를 풀어보면서 느낀 결과 sliding window도 부분 배열의 크기가 변하기는 하지만, 한쪽 방향으로 꾸준히 부분 배열을 감싸는 창문이 이동하는 느낌이고 two pointers는 양쪽을 비교하여 어느 쪽으로 이동할지 + 크기 조정이 되는 것 같다.
