Sliding Window - findLongestSubstring
서론
패턴에 관해서는 이 글이 마지막 코드 리뷰이다.
마지막 문제답게 좀 난이도가 있었는지 다른 문제를 풀 때보다 더 많은 시간이 소요됐다.
마지막에 마지막에 가서는 도저히 안되겠어서 살짝 해설을 참고하기도 했는데...
그래도 결론적으로 잘 풀어냈고 문제를 이해했음을 보여주기 위해 리뷰를 작성해 보겠다!
본론
findLongestSubstring은 인자로 받은 string에서 글자가 중복되지 않는 가장 긴 substring의 길이를 반환해야하는 함수이다. 내가 처음 선택한 방법은 다음과 같다.
- 문자열을 객체에 저장하면서 비교
- 문자가 중복된다면 윈도우 시작점으로 오른쪽으로 이동. > maxLen갱신
- 문자가 중복이 아니라면 윈도우 끝을 오른쪽으로 이동, 객체에 문자 저장.
이런 방식으로 진행하다 보면 중복된 문자가 있을 경우 중간에 진행하지 못하고 무한루프에 빠지게 되는것 같다. 내가 초기에 시도했던 코드는 다음과 같다.
for(let i = 0; right < str.length - 1; i++){
if(lookup[str[right + 1]]{
maxLen = Math.max(maxLen, right - left + 1);
left++;
}else{
lookup[str[right++]] = 1;
right++;
}
}다음과 같이 중복되지 않을 때에만 윈도우의 끝을 오른쪽으로 이동시킬 수 있는데, 이런 경우 중복되는 글자가 있으면 영원히 right가 제자리 걸음을 하기 때문에 무한루프에 빠져 콘솔이 마비되곤 했다. 이 무한 루프를 빠져나오기 위해서는 시작점과 끝점을 다른 방식으로 재세팅할 필요가 있었다. 해설에서 제시한건 인덱스를 이용하는 것이다.
for(let i = 0; i < str.length; i++){
if(lookup[str[i]]){
//이미 존재하는 인덱스 중 큰 것을 다시 세팅
left = Math.max(left, lookup[str[i]]);
}
maxLen = Math.max(maxLen, i - left + 1);
//인덱스를 세팅 길이 계산을 해야하니 +1
lookup[str[i]] = i+1;
}나는 존재함을 나타내기 위해 새로 문자를 객체에 등록할 때 1로 등록을 했다. 하지만 다음처럼 해당 인덱스를 문자의 value로 등록하는 것으로 해당 인덱스를 이용하여 처음 시작점을 다시 세팅한 것이다. 위와 같이 같은 문자열이 나오지 않을 때까지 비교할 필요없이 문자열의 길이만큼만 비교하면 되는 것이니 성능 부분에서도 내가 처음 선택한 방법보다 훨씬 좋았다.
참고
웹개발