Udemy - 포인터 기본 예제

---

1️⃣  빈도수 체크 (같은 빈도수 찾기)

두 개의 정수의 자릿수들이 서로 빈도수가 일치하는지 체크 !

function sameFrequency(a, b) {
  // 나 같은 경우엔 두 정수들을 toString해서 문자열로 바꾼 뒤 풀이했다.
  let aStr = a.toString();
  let bStr = b.toString();
  // 당연히 두 인풋의 길이가 다르면 각 빈도수도 절대 같을 수 없다.
  if (aStr.length !== bStr.length) {
    return false;
  }
  let checker = {};
  // a의 각 자리수가 몇개씩 들어있는지 오브젝트로 만든다.
  for (let i = 0; i < aStr.length; i++) {
    checker[aStr[i]] ? (checker[aStr[i]] += 1) : (checker[aStr[i]] = 1);
  }
  for (let i = 0; i < bStr.length; i++) {
    if (!checker[bStr[i]]) {
      return false;
    } else {
      checker[bStr[i]]--;
    }
  }
  return true;
}

---

2️⃣  빈도수 체크 (다중 포인터 사용)

주어진 입력값들 중에 중복값이 있는지 체크하는 다중포인터 함수 짜기

• 나의 풀이

  function areThereDuplicates(...input) {
    let list = {};
    input.map((item) => (list[item] ? (list[item] += 1) : (list[item] = 1)));
    for (let val in list) {
      if (list[val] > 1) {
        return true;
      }
    }
    return false;
  }

• 다중포인터 풀이법

  function areThereDuplicates(...args) {
    // 아.. sort를 사용해도 되는지 몰랐다 ㅜ (시간복잡도에 어떤 영향을 줄지 몰랐음)
    args.sort((a, b) => a > b);
    let start = 0;
    let next = 1;
    while (next < args.length) {
      if (args[start] === args[next]) {
        return true;
      }
      start++;
      next++;
    }
    return false;
  }

• O$$(nlog_n)$$ 풀이방법
  🤔 Set()이란?
  ⇒ Set은 하나의 객체로, 자료형에 관계 없이 유일한 값만을 저장할 수 있다. 즉, Set()오브젝트에 담기게 되면 중복된 값이 제거된다.
  ⇒ object.has(), object.size 등을 통해 특정 값의 포함 여부와 객체의 길이를 측정할 수 있다.

  function areThereDuplicates(...args) {
    // 중복이 제거된 배열 -> 객체화 -> 사이즈가 기존 배열의 길이와 다르면 중복값이 존재한다는 뜻이다.
    return new Set(args).size !== args.length;
  }

---

3️⃣  다중 포인터 ( 평균값 묶음 찾기 )

주어진 입력 정수 리스트 중에, 주어진 평균값이 도출될 수 있는 묶음이 있는지 여부를 반환하는 함수 작성!

• 나의 풀이

  function averagePair(arr, target) {
    // 배열이 빈 배열이면 무조건 false
    if (arr.length === 0) {
      return false;
    }
    // 다중 포인터에서 앞 부분의 포인터는 start, 뒤의 포인터는 end로 선언했다.
    let start = 0;
    let end = start + 1;
    // i는 두 포인터 사이의 간격이다.
    let i = 0;
    // 아래에서 사용될 arr[start]~arr[end]까지의 합을 구하기 위한 함수다.
    const sumMaker = (input) => {
      return input.reduce((prev, cur) => prev + cur);
    };
    // 두 포인터의 간격은 배열의 길이 -2까지만 허용된다.
    // 따라서, arr.length - 1보다 작을 때 까지만 반복문이 실행되어야 한다.
    while (i < arr.length - 1) {
      // 만약 end 포인터가 배열의 끝에 닿으면 간격을 늘리고 다시 처음 묶음부터 체킹해야 된다.
      if (end > arr.length - 1) {
        // 간격을 늘리고
        i++;
        // 두 포인터의 위치 또한 초기화 시킨다.
        start = 0;
        end = start + i + 1;
      }
      // 배열을 두 포인터까지로 잘라낸다.
      let sliced = arr.slice(start, end + 1);
      // 합을 구하고, 이를 통해 평균을 구한다.
      let sum = sumMaker(sliced);
      let avg = sum / sliced.length;
      // 만약 구한 평균값과 target값이 같으면 true를 반환한다.
      if (avg === target) {
        return true;
      } else {
        // 그게 아니라면, 두 포인터를 한칸씩 이동시킨다.
        start++;
        end++;
      }
    }
    // 반복문을 마쳤는데도 true가 안나왔으면 false인거다.
    return false;
  }

---

4️⃣  다중 포인터 ( 부분 문자열 찾기 )

첫 째 입력값(String)의 character들이 두 번째 입력값(String)에 모두 포함되는지 체크하는 함수를 작성
단, 첫 째 입력값의 순서가 뒤바뀌어서는 안된다.

• 나의 솔루션 코드 ( 애 좀 먹었다… )

  function isSubsequence(a, b) {
    // a 문자열의 길이가 더 길면 정답일 수가 없다.
    if (a.length > b.length) {
      return false;
    }
    // 추출 결과가 담길 test 배열을 만든다.
    let test = [];
    // a,b 두 문자열을 모두 배열에 담는다.
    let aArr = [...a];
    let bArr = [...b];
    // 포인터 두 개 만들기
    let i = 0;
    let j = 0;
    while (i < aArr.length) {
      // i는 a를, j는 b를 순회하며 체크한다.
      // 만약 두 배열의 요소 값이 같아지는 경우가 발생하면 해당 값의 첫 번쨰 index값을 test에 담는다.
      if (bArr[j] === aArr[i]) {
        test.push(bArr.indexOf(bArr[j]));
        // a는 이제 다음 요소를 체크해도 되므로 i++해준다.
        // j는 다시 0으로 초기화 시킨다.
        i++;
        j = 0;
      } else {
        // 같지 않으면 j++ 시키며 계속 순회하도록 한다.
        j++;
      }
      // 하지만 j가 끝에 닿으면 0으로 초기화 시키고, i또한 다음으로 넘긴다.
      if (j === bArr.length) {
        j = 0;
        i++;
      }
      // 이미 요소들이 다 담겼는데 끝까지 반복문을 돌릴 필요는 없다.
      if (test.length === aArr.length) {
        break;
      }
    }
    // 만약 test에 담긴 각 요소들의 index값이 오름차순이 아니면 이는 false를 출력할 것이다.
    return test.reduce((prev, cur) => prev < cur);
  }

• 반복문 풀이법 (현타… 온다…)

  function isSubsequence(str1, str2) {
    var i = 0;
    var j = 0;
    if (!str1) return true;
    while (j < str2.length) {
      if (str2[j] === str1[i]) i++;
      if (i === str1.length) return true;
      j++;
    }
    return false;
  }

• O(1) 풀이법 (하….)

  재귀함수를 사용했는데, 굉장히 획기적인 풀이 방법인 것 같다.

  function isSubsequence(str1, str2) {
    if (str1.length === 0) return true;
    if (str2.length === 0) return false;
    if (str2[0] === str1[0]) return isSubsequence(str1.slice(1), str2.slice(1));
    return isSubsequence(str1, str2.slice(1));
  }

---

5️⃣  Sliding Window ( 최대값 찾기 )

주어진 숫자의 묶음 중에서 최대값을 찾는 알고리즘을 작성
단, 묶음은 연속된 요소로만 구성된다.

• 나의 솔루션 코드 : O(N)

  function maxSubarraySum(arr, num) {
    if (arr.length < num) {
      return null;
    }
    // 일시적 합을 담을 temp, 최대값을 담을 max
    let temp = 0;
    let max = 0;
    // 우선 0~num까지의 합을 temp와 max에 담아줌
    for (let i = 0; i < num; i++) {
      temp += arr[i];
    }
    max = temp;
    // temp에서 이전 첫째값을 빼고, 그 다음 값을 더해주고 max와 비교
    // 더 큰 값이 max에 담긴다.
    for (let i = num; i < arr.length; i++) {
      temp = temp - arr[i - num] + arr[i];
      max = Math.max(temp, max);
    }
    return max;
  }

---

6️⃣  Sliding Window ( 최소 길이 찾기 )

각 요소의 값의 합이 num이 되는 조합 중, 가장 짧은 길이를 갖는 조합의 length를 출력하는 알고리즘 작성

• 나의 솔루션 코드 : O(N)

  function minSubArrayLen(arr, num) {
    let sum = 0;
    let start = 0;
    let end = 0;
    let minLen = Infinity;
    while (start < arr.length) {
      if (sum < num && end < arr.length) {
        sum += arr[end];
        end++;
      } else if (sum >= num) {
        minLen =
          start === 0
            ? Math.min(minLen, end - start + 1)
            : Math.min(minLen, end - start);
        sum -= arr[start];
        start++;
      } else {
        break;
      }
    }
    return minLen === Infinity ? 0 : minLen;
  }

---

7️⃣  Sliding Window ( 가장 긴 독립 문자열 찾기 )

주어진 문자열에서 중복되지 않는 Character가 어디까지 이어지는지 그 길이를 출력하는 알고리즘을 작성

• 나의 솔루션 코드

  function findLongestSubstring(input) {
    if (input.length === 0) {
      return 0;
    }
    // 초기 최대값 가장 작은 값으로 설정
    let max = -Infinity;
    // 독립적 문자들을 담을 checker 객체를 생성
    let checker = {};
    let i = 0;
    let j = i;
    while (i < input.length) {
      // j포인터가 끝에 닿았거나, 해당 글자가 checker 오브젝트에 존재한다면?
      if (j === input.length || checker[input[j]]) {
        // max값 갱신
        max = Math.max(max, j - i);
        // checker는 다시 초기화
        checker = {};
        // i++ -> 가장 처음값 담음
        i++;
        checker[input[i]] = 1;
        // j는 i의 다음값부터 체크하면 되므로 i+1로 초기화
        j = i + 1;
      } else {
        checker[input[j]] = 1;
        j++;
      }
    }
    return max;
  }

---