Portfolio

📄문제

✏️풀이

은찬


const lengthOfLongestSubstring = (s) => {
    let length = 0;
    
    for(let i = 0; i < s.length; i++){
        const substrings = new Map();
        let string = "";
        
        for(let j = i; j < s.length; j++){
            if(!substrings.get(s[j])){
                substrings.set(s[j], true);
                string += s[j];
            } else{
                break;
            }
        }
        
        length = length < string.length ? string.length : length;
    }
    
    return length;
};

효성

실패한 풀이


var lengthOfLongestSubstring = function(s) {
    if(s.length === 0) {
        return 0;
    }
    let max = 0;
    
    for(let i=0; i<s.length-1; i++) {
        if(checkRepeat(s.slice(i))) {
            let res = checkRepeat(s.slice(i));
            max = max > res ? max : res;
        }
    }
    
    return max;

};

function checkRepeat(str) {
    let longest = [];
    for(let i=0; i<str.length; i++) {
        if(longest.includes(str[i])) {
            return longest.length;
        }
        longest.push(str[i]);
    }
}

참고한 풀이


var lengthOfLongestSubstring = function(s) {
  var sLen = s.length,
    maxLen = 0,
    maxStr = '',
    tmpStr,
    posIndex,
    i;

  for( i = 0 ; i < sLen; i++ ){

    tmpStr = s[i];
    posIndex = maxStr.indexOf(tmpStr);

    if(posIndex > -1){
      maxStr = maxStr.substring(posIndex + 1);
    }

    maxStr += tmpStr;
    maxLen = Math.max(maxLen, maxStr.length);
  }

  return maxLen;
};

💡

substring은 중복된 문자를 제거하고 그 뒤에 제거한 중복 문자를 다시 붙여주려는 의도임.

실패한 풀이를 성공으로 이끈 은찬님의 풀이


var lengthOfLongestSubstring = function(s) {
    if(s.length === 0) {
        return 0;
    }
    let max = 0;
    
    for(let i=0; i<s.length; i++) {
        if(checkRepeat(s.slice(i))) {
            let res = checkRepeat(s.slice(i));
            max = max > res ? max : res;
        }
    }
    
    return max;

};

function checkRepeat(str) {
    let longest = [];
    for(let i=0; i<str.length; i++) {
        if(longest.includes(str[i])) {
            break;
        }
        longest.push(str[i]);
    }
        
    return longest.length;
}

💡

문자열이 1개일 때 checkRepeat 함수가 if문을 통과하지 않았기 때문.

재영

제가 생각했던 건 이걸 한 큐에 풀 수 있으면 어떨까 싶었어요.

그렇다면 for문으로 풀면 전제 되어야 할 것이 어떤 것인지로 접근했어요!

그 결과 다음과 같았답니다.

💡

1. 만약 for문으로 돌린다면, 계속해서 maxCount가 기억이 되어야 한다. 2. 그렇다면 현재의 개수 역시 기억을 해주며, 계속해서 조건에 따라 업데이트 한다. 3. 조건마다 계속해서 현재의 개수를 업데이트 해주어야 한다.

따라서 이를 토대로 접근했습니다.

(1)의 경우 → let maxCnt = 0;

(2)의 경우 → let cnt = 0;

(3)의 경우: 크게 2갈래로 나뉘어지겠죠.

for문을 순회할 때 현재의 문자가 중복되는 경우와 - #1

중복되지 않는 경우로 말이죠. -#2

(5) # 1 - 만약 현재 문자가 중복되는 경우라면... 과감히 cnt를 초기화시켜줘야 한다.

초기화의 기준을 세우기 위해 lastIndices라는 걸 만들어줬다. 이 친구는 해당 문자가 언제가 마지막이었는지를 기억한다.

만약 저 친구보다 [현재 인덱스] - [카운트] 가 같거나 더 작다면?

결과적으로 저 lastIndices를 포함하고 있다는 것이므로 중복이 되는 것이다.

따라서 다시 초기화를 시켜줘야 하는데... 이는 [현재 인덱스] - [이전 마지막으로 기억해준 인덱스]가 될 것이다.

(5) # 2 - 아니라면 그저 1을 더해서 계산해주면 될 것이다. 또한, maxCount와 비교해서 더 크다면 업데이트를 해준다.

모든 조건이 끝났다. 값을 출력해준다.


const lengthOfLongestSubstring = (s) => {
  let maxCnt = 0;
  let cnt = 0;
  const lastIndices = {};
  s.split("").forEach((char, idx) => {
    if ((lastIndices[char] ?? -1) < idx - cnt) {
      // idx - cnt : 현재 찾는 길이의 첫 번째 문자 인덱스 위치.
      cnt += 1;
      maxCnt = Math.max(maxCnt, cnt);
    } else {
      cnt = idx - lastIndices[char];
    }
    lastIndices[char] = idx;
  });
  return maxCnt;
};

💡

왜 갑자기 존댓말 하다가 반말로 이어졌는지는 모르겠다. 이것이 진정한 반존대일까?🤥

Longest Substring Without Repeating Characters

📄문제

✏️풀이

실패한 풀이

참고한 풀이

실패한 풀이를 성공으로 이끈 은찬님의 풀이