leetcode [3]

1번과 2번은 잘 풀었는데, 3번 문제에서 순위권에서 최하를 기록했다.

즉석에서 작성한 코드여도 갑자기 최하의 성능을 평가받으니, 더 나은 코드가 무엇인지 왜 그런 차이가 발생하는지 궁금했다.

var lengthOfLongestSubstring = function(s) {
    let max = 0;
    let temp = [];
    //외부 루프는 문자열 s의 각 문자를 반복
    for (let i = 0; i < s.length; i++) {
 		// 내부 루프는 현재 문자부터 시작하여 가능한 모든 하위 문자열을 확인
        for (let e = i; e < s.length; e++) {
          	// 하위 문자열에 반복되는 문자가 포함되어 있으면 내부 루프에서 벗어나 외부 루프의 다음 반복을 진행합니다.
            if (temp.includes(s[e]) == true || e < temp.length) {
                break;
            }
          	// 현재 부분 문자열에 반복되는 문자가 포함되어 있지 않으면 임시 배열에 문자를 추가
            temp.push(s[e]);
            console.log(e + 'th small cycle, temp : ' + temp);
          	// 임시 배열의 길이가 지금까지 표시된 최대 길이(최대)보다 큰지 확인합니다. 길이가 더 크면 최대 값을 업데이트합니다.
            if (temp.length > max) {
                max = temp.length;
                console.log(e + 'th small cycle, max : ' + max);
            }
            
        }
        console.log(i + 'th big cycle, temp : ' + temp + ', max : ' + max);
      	// 마지막으로 임시 배열을 지우고 외부 루프의 다음 문자로부터 새 하위 문자열로 시작합니다.
        temp = [];
        
    }
    return max;
};

----input----
s = "pwwkew"
----result (Runtime: 100 ms)---- 
0th small cycle, temp : p
0th small cycle, max : 1
1th small cycle, temp : p,w
1th small cycle, max : 2
0th big cycle, temp : p,w, max : 2
1th small cycle, temp : w
1th big cycle, temp : w, max : 2
2th small cycle, temp : w
3th small cycle, temp : w,k
4th small cycle, temp : w,k,e
4th small cycle, max : 3
2th big cycle, temp : w,k,e, max : 3
3th small cycle, temp : k
4th small cycle, temp : k,e
5th small cycle, temp : k,e,w
3th big cycle, temp : k,e,w, max : 3
4th small cycle, temp : e
5th small cycle, temp : e,w
4th big cycle, temp : e,w, max : 3
5th small cycle, temp : w
5th big cycle, temp : w, max : 3

GPT : "이 코드는 가능한 모든 하위 문자열을 고려하여 문제를 해결하기 위해 무차별 대입 방식을 사용합니다.
1. 외부 루프는 문자열 s의 각 문자를 반복
2. 내부 루프는 현재 문자부터 시작하여 모든 하위 문자열을 확인
3. 두 개의 중첩된 루프를 초기화"

이 접근 방식은 문자열의 각 문자에 대해 해당 문자에서 시작하여 가능한 모든 하위 문자열을 확인하고 각 하위 문자열에 대해 반복되는 문자가 포함되어 있는지 확인하기 때문에 시간 복잡도가 O(n^3)입니다.

이유를 gpt에게 물어보니 루프를 중첩시켜서 시간 복잡도가 O(n^3)이 되었다고 함.

지금은 처리할 문자열의 개수가 작아서 괜찮을 뿐이지, 개수가 많아진다면 속도가 최악으로 떨어진다는 것이다.

빅오표기법은 알고리즘이 걸리는데 필요한 시간의 수학적인 표현이라고 할 수 있습니다.
일반적으로 최악의 시나리오를 상정했을 때의 복잡도를 의미합니다.

var lengthOfLongestSubstring = function(s) {
    let max = 0;
    let temp = new Set();
    let i = 0, j = 0;
    
    while (i < s.length && j < s.length) {
        if (!temp.has(s[j])) {
            temp.add(s[j++]);
            max = Math.max(max, j - i);
        } else {
            temp.delete(s[i++]);
        }
    }
    
    return max;
};

GPT가 잘못된 부분을 잘 지적해주고 이렇게 써보면 어떠냐고 제시하였다.

1. Set의 사용
2. i와 j 변수 동시 사용
3. temp에 s의 j번째 문자열 있는지 체크
   3-1. 없다면 temp에 s의 j번째 문자열 삽입 후 j+1 증가
   3-2. 없다면 현재의 max의 값, j - i값과 큰 값을 max에 삽입
   3-3. 있다면 s의 i번째 문자열을 temp 에서 삭제 후 i+1 증가
4. max를 반환

temp와 max의 사용은 같지만, Set방식과 증가연산자를 잘 사용하여 반복문을 중첩시키지 않았다.