[Day 3] 한 문자열에서 중복되는 단어가 없는 가장 긴 문자의 길이 찾기

📅 2022.10.06
📖 파트너 : 모유진

문제설명 :
String 형인 str 인자에서 중복되지 않은 알파벳으로 이루어진 제일 긴 단어의 길이를 반환해주세요.

• str: 텍스트
• return: 중복되지 않은 알파벳 길이 (숫자 반환)

예시
str = "abcabcabc"
return 은 3
=> 'abc' 가 제일 길기 때문

str = "aaaaa"
return 은 1
=> 'a' 가 제일 길기 때문

str = "sttrg"
return 은 3
=> 'trg' 가 제일 길기 때문

1. Stack을 활용한 풀이 (오답)

오답이면서 너무 길어서 설명하는게 의미가 있겠나 싶지만 나의 생각의 흐름을 되짚어보기 위함이다.

처음에는 문제의 의도를 잘못 해석해서 그냥 반복된것만 제거하면 되는것 아닌 가 라고 생각했다.

실제로 예시로 들어준 케이스는 단순히 중복된 값만 제거해줘도 정답이 도출 된다. 그런데 테스트가 통과가 되지 않아 다른 방법을 생각하다가 st trg로 나뉘어 진다는 생각에 stack 문제가 아닐까 생각했다. 문자열을 순회하면서 임시로 문자를 담아줄 빈배열 stack을 만들고 stack과 stack에 담길때 str 배열에서는 요소를 삭제함으로써 str와 stack의 길이를 비교하는 방식으로 접근을 했는데 이것도 문제의 이해가 잘못된 것이다.

만약 입력값이 st trg 이면 각각 배열 길이를 비교할때 문제가 되지 않겠지만 zabc adefg 인 경우 a 라는 문자를 두번째로 만났을 때 배열이 나뉘어 져 실제 값인 bcadefg와는 다르게 된다

if (!Array.prototype.peek) {
  Array.prototype.peek = function() {
    return this[this.length - 1];
  };
}

if (!Array.prototype.isEmpty) {
  Array.prototype.isEmpty = function() {
    return this.length == 0;
  };
}
const getLengthOfStr = str => {
  // 아래 코드를 작성해주세요.
  let arr = str.split("");
  let stack = [];
  let length = [];

  for (let i = 0; i < arr.length; i++) {
    if (!stack.includes(arr[i]) || stack.isEmpty()) {
      stack.push(arr[i]);
      length.push(stack.length);
    }else {
        let findIndex = stack.indexOf(arr[i]);
        console.log(findIndex);
        stack.splice(0, findIndex + 1);
        stack.push(arr[i]);
        length.push(stack.length);   
    }
  }

  return Math.max(...length);
}

그래서 stack 배열에 담되 array배열은 변화시키지 않으면서 for문을 이용해 str배열의 요소가 stack 배열에 있는지 없는지만 확인하고 만약에 stack 배열에 없다면 요소를 push해 stack 배열을 업데이트하고 만약에 stack 배열에 요소가 있다면 처음부터 stack배열 안에 중복된 요소의 인덱스까지 stack 배열에서 삭제 시켜야 했다.

그래서 indexOf 메서드로 arr[i]의 위치를 찾고 splice(시작할 위치, 삭제할갯수)로 삭제할 갯수에 index+1 을하여 해당 요소를 포함하여 삭제를 시켰다. 그리고 stack에 arr[i]를 다시 추가하여 stack이 이어질 수 있게 로직을 짰는데 테스트에서 한문제 틀리는 결과로 나왔다.

어떤케이스에서 오답이 나는지 아직 찾는 중이다

---

2. 스택을 사용하지 않고 새로운 문자열 배열에 축적하는 방법

const getLengthOfStr = str => {

  if (str.split('').length === 0) { return 0; }
  let num = "";
  let arr = [];
  for (let i in str) {
    if (num.includes(str[i])) {
      num = num.slice(num.indexOf(str[i]) + 1)
    }
    console.log(num);
    num += str[i];
    arr.push(num.length);
  }

  return Math.max(...arr);
  }
};

이 코드를 짤 때 유의해야 할 점은

• num 이라는 비어있는 문자열을 만들고 각각 case 마다 길이를 반환해줄 arr 라는 빈 배열을 만드는데 부터 시작한다

• str 문자열을 for...in 으로 순회하면서 문자열 알파벳 하나하나 num str에 포함되는지 조건을 건다

• num 문자열이 str[i]을 포함하고 있다면 num 값을 num에서 str[i]까지 있는 배열을 잘라낸 값으로 slice(갯수) (찾은 index+1을 해주어야 str[i] 까지 잘라줌)

  splice(시작할인덱스번호, 삭제할갯수) : 배열에서만 사용가능 원본배열이 바뀜
  slice(삭제할갯수) : 문자열에 사용가능 원본배열은 바뀌지 않으므로 재할당해야함 첫번째 요소부터 삭제된다

• 문자열이 str[i] 요소를 포함하고 있지 않다면 num에 str[i] 요소를 증감연산자로 더해준다 (string + num = string)

• 길이를 담아줄 배열에 num문자열의 길이를 푸시하고

• 포문을 다 돌고 나면 (num문자열의 길이 축적)

• Math.max(배열)로 최대값을 구해준다

---

3. 링크로 문제 생각해보자

풀다 보니 기차 처럼 연결되어 있다는 생각을 했다 같은 문자를 만나게 되면 link를 삭제해주는 형식으로 풀어도 될것같다