✔️ 2. Multiple Pointers

1. 인덱스 또는 위치 해당하는 포인터와 값을 생성하고 특정 조건 기준으로 처음 끝 중간으로 이동.
   -> 공간 복잡성을 최소화하면서 문제를 해결하는데 효율적
2. 한 쌍의 값이나 조건을 충족시키는 것을 찾는 방식 (보통은 한 쌍을 찾는데 사용)
3. 두 개의 포인터를 생성
   -> 투 포인터라고도 부름

💻 예제 1

정렬된 정수의 배열를 받아 합이 0이 되는 한쌍의 숫자를 배열 형태로 리턴하는 sumZero 함수를 작성하시오.
(합이 0인 한 쌍이 존재하지 않으면 undefined 리턴)

sumZero([-3,-2,-1,0,1,2,3]) // [-3,-3]
sumZero([-2,0,1,3]) // undefined
sumZero([1,2,3]) // undefined

🔎 내가 했던 풀이

🔸 풀이 전 어떻게 구성할지 생각해봤다

1. 다중포인터 -> 한쌍의 값을 찾으므로 포인터를 두 개 사용 한다?
2. 처음 끝 양쪽에서부터 이동하며 비교

• 합이 0 이면 한쌍의 배열 리턴
• 합이 양수 끝 포인터 -- (오른쪽 양수가 더 크니까)
• 합이 음수 시작 포인터 ++ (왼쪽 음수가 더 크니까)
• 끝 포인터 - 시작 포인터 => 음수라면 비교 끝 return

🔸 위의 내용을 코드로 구성해보면

const sumZero = (intArr) => {
  

  let left = 0; //첨
  let right = intArr.length - 1; //끝
  while (left < right) {
    const sum = intArr[left] + intArr[right];
    if (sum === 0) return [intArr[left], intArr[right]];
    else if (sum > 0) right--;
    else left++;
  }
};

시간 복잡도 O(N), 공간 복잡도 O(1) => 해답도 내가 했던 풀이와 동일했다 🤓

시간 복잡도를 생각하지 않고 `nested loop`를 사용한 코드는 어떤걸까? 아래와 같다!

아래의 코드의 성능의 경우 시간복잡도 O(n^2) , 공간 복잡도 O(1)와 같다.

const sumZeroUseNL = (intArr) => {
  for (let i = 0; i < intArr.length; i++) {
    for (let j = j + 1; j < intArr.length; j++) {
      if (intArr[i] + intArr[j] === 0) {
        return [intArr[i], intArr[j]];
      }
    }
  }
};

🔎 풀이

내가 했던 풀이와 동일~!

💻 예제 2

정렬된 정수의 배열을 받아 배열의 고유값의 갯수를 리턴하는 countUniqueValues 함수를 작성하시오
(음수가 올 수 있다, 배열은 항상 sort된 상태이다)

countUniqueValues([1,1,1,1,1,2])//2
countUniqueValues([1,2,3,4,4,4,5,5,12,12,13]) //7
countUniqueValues([])//0
countUniqueValues([-2,-1,-1,0,1]) //3

🔎 내가 했던 풀이

🔸 풀이 전 어떻게 구성할지 생각해봤다

• 음수가 배열의 요소로 올 수 있음 -> ex) [-1,1] => -1과 1 고유값 2가지
  • 포인터 2개 선언
  • 두개의 포인터를 증가 시키면서 서로 비교,
  • 선증가된 비교값의 포인터가 배열의 마지막 인덱스가 되면 종료 후 갯수 반환
  • 빈 배열을 받으면 무조건 0 리턴 => 따라서 count의 초기값은 1
  처음에 음수를 고려하지 않는 절대값을 비교하는 줄 알고 삽질했었다.. 해당 문제의 의도를 다시 잘 파악해보자...ㅋ..😩

🔸 위의 내용을 코드로 구성해보면

const countUniqueValues = (intArr) => {

  if (intArr.length === 0) return 0;

  let basis = 0;
  let round = 1;
  let count = 1;

  while (round < intArr.length) {
    const baseElem = intArr[basis];
    const roundElem = intArr[round];

    if (baseElem !== roundElem) count++;

    basis++;
    round++;
  }

  return count;
};

🔎 풀이

while을 사용한 풀이 => 알고리즘 풀이 과정만 보고 다시 구성해 봄!

const solCountuniqueValues = (intArr) => {
  if (intArr.length === 0) return 0; // 빈 배열은 비교 할 필요 없으니 바로 0 리턴

  let basis = 0;
  let round = 1;

  while (round < intArr.length) {

    if (intArr[basis] !== intArr[round]) {
      basis++;
      intArr[basis] = intArr[round];
    }

    round++;
  }

  return basis + 1;
};

1)변수선언
basis : 기준점
round : index를 증가시키며 비교하는 값
2)과정
basis와 round 위치의 같으면 round 인덱스 증가
basis와 round 위치의 값이 다르면 basis 인덱스 증가 후 해당 자리에 비교값 할당, round 인덱스 증가
3)리턴값
해당 작업 반복 후 round의 인덱스가 배열 마지막 인덱스가 되면 basis 의 index+1(인덱스는 0부터 시작하므로) 리턴

위의 내용을 for loop를 이용해 다시 리팩토링😎

• 불필요한 변수 할당 줄이기 , 필요한 변수 1개만 선언

//풀이

const solCountuniqueValues = (intArr) => {
  if (intArr.length === 0) return 0; // 빈 배열은 비교 할 필요 없으니 바로 0 리턴
  let i = 0;
  for (let j = 0; j < intArr.length; j++) {
      if(intArr[i] !== intArr[j]) {
      i++;
      intArr[i] = intArr[j];
      }
  }

  return i + 1;
};