[21/10/06] Longest Substring Without Repeating Characters By Sliding Window

rat8397·2021년 10월 6일
0

코드카타

목록 보기
33/44
post-thumbnail

문제

코드

1차 코드

문자열을 한개로 쪼갤때, 두개로 쪼갤때 -> 마다 문자열을 전부 쪼개어 중복이 있는지 없는지 검사한 후 중복이 없는 것이 있다면 answer을 갱신한다.

최악의 경우 n^2 * (slice하는 시간 + 중복 체크를 위해 set을 만드는 시간) 비효율적이다.

/**
 * @param {string} s
 * @return {number}
 */
var lengthOfLongestSubstring = function(s) {
    if(s.length === 0) return 0;
    
    let answer = 1;
    
    for(let num = s.length-1;num>=0;num--){
        
        
        for(let i=0;i<= s.length - (num+1);i++){
               
            if(!isDuplicate(s.slice(i,i+(num+1)))){
                
                return num+1;
                
            }
        
        }
    }
    
    
    function isDuplicate(s){
        const array = s.split("");
        return [...new Set(array)].length !== array.length
    }
};

2차 코드

슬라이딩 윈도우를 적용해보았다. O(n)시간에 끝낼 수 있다.

var lengthOfLongestSubstring = function(s) {
    
    const chars = [];
    
    let answer = 0;

    for(let i=0;i<s.length;i++){
    
        while(chars.indexOf(s[i]) !== -1){
            // 중복되는 것이 나왔다면, 해당 문자를 지우지 않는 이상 모두 불가능하다. 따라서 큐에 넣었던 걸 다 삭제하고 (중복문자까지) 다시 시작한다고 생각해야함.
          
            // 최악의 경우 n의 시간이 소비되지만, 최악의 경우라면 이전 반복에서 이 반복문을 실행하지 않게 된다.
            
            
            chars.shift();
        }

        chars.push(s[i]);
        
        answer = Math.max(chars.length,answer);
        
        
    }
    return answer;

};

//while 문을 다음과 같이 작성하면 살짝 성능이 떨어진다. -> 반복문에 항상 들어가고 항상 break를 실행시켜서 그런가..?
 while(true){
            
            if(chars.indexOf(s[i]) === -1){
        
                break;
            
            }
            chars.shift();
     }

map 객체를 이용하여 풀수도있다. left - right 가 window의 범위이다.

var lengthOfLongestSubstring = function (s) {
  let map = new Map();
  let left = 0;
  let max = 0;

    
    for(let right=0;right<s.length;right++){
        const char = s[right];
        
        if(map.has(char) && map.get(char) >= left){
            // 중복이 발생한 이 후 부터 다시 시작.
            // 중복이 발생한 문자이면서 현재 문자 범위에 속해있다면 left를 그 문자 위치 + 1해주어야한다. 
            
            left = map.get(char) + 1;
        }else{
            // 처음 등장한 문자이거나, 중복이 발생하였으나 현재 문자 창 범위에 있지 않은 경우
            max = Math.max(max,right-left + 1);     
        }
        
        map.set(char,right);
    
        
       
    }
    
    

  return max;
};

슬라이딩 윈도우 - 손 코딩

profile
Frontend Ninja

0개의 댓글