투포인터스 알고리즘으로 푸는 방법이 제가 이해한게 맞을까요?

제가 이해한 걸로는 두개의 포인터 변수를 이용하여서 반복문을 하나를 가지고 문제를 푸는거라고 이해를 해서 아래와 같이 하나의 반복문으로 풀려고 노력했는데 해당 알고리즘이 제가 이해한 이론이 맞나요?

function solution(arr1, arr2) {
        let answer = [];
        let sorArr1 = arr1.sort((a, b) => a - b);
        let sortArr2 = arr2.sort((a, b) => a - b);
        let n = sorArr1.length;
        let m = sortArr2.length;
        let p1 = (p2 = 0);

        while (p1 < n) {
          if (sorArr1[p1] === sortArr2[p2]) {
            answer.push(sorArr1[p1]);
          }

          p2++;

          if (p2 === m - 1) {
            p1++;
            p2 = 0;
          }
        }

        return answer;
      }

      console.log(solution([1, 3, 9, 5, 2], [3, 2, 5, 7, 8]));

정답은 잘 나옵니다만... 핵심이 두개의 포인터 변수와 하나의 반복문만 사용한다 라고 기억 할려고 하는데 이게 맞을지...

안녕하세요, 인프런 AI 인턴입니다.
rhkdtjd_12님, 투 포인터스 알고리즘에 대한 이해가 꽤 잘 잡혀 있는 듯하네요.

예, 맞습니다. 투 포인터 알고리즘은 두 개의 포인트를 이용해서 주로 정렬된 배열에서 두 수의 합이나 차 같은 특정 조건을 만족하는 쌍을 효율적으로 찾는 데 사용됩니다. 보통 이 때 두 포인터는 각각 배열의 시작점과 끝점, 혹은 두 배열의 시작점에서 출발하는데, 포인터가 움직이는 조건에 따라 반복문 내에서 여러 상황을 처리할 수 있습니다.

제시해주신 코드를 보면 두 배열의 정렬된 원소들을 비교하며 공통된 값을 찾는 문제를 푸는 것으로 보입니다. 이런 종류의 문제 해결에 투 포인터 알고리즘이 적절히 사용된 경우라고 볼 수 있습니다. 다만, p2 포인터의 증가 조건과 p1 포인터의 증가 조건을 다시 살펴볼 필요가 있어요.

정확한 투 포인터 알고리즘은 두 배열의 각각의 포인터를 시작점에 놓고, 각 포인터가 가리키는 원소를 비교하며 두 포인터를 각각의 조건에 따라 이동시키면서 정답을 찾아나갑니다. 만약 sorArr1[p1]이 sortArr2[p2]보다 크다면 p2를 증가시켜야 하고, 반대의 경우에는 p1을 증가시켜야 하는 식으로 말이에요. 코드에서 p2 === m - 1 일 때만 p1을 증가시키고 있어서, 일반적인 투 포인터 알고리즘의 접근과는 조금 다릅니다.

아래는 수정된 코드 예시입니다.

function solution(arr1, arr2) {
  let answer = [];
  let p1 = 0, p2 = 0;

  arr1.sort((a, b) => a - b);
  arr2.sort((a, b) => a - b);

  while (p1 < arr1.length && p2 < arr2.length) {
    if (arr1[p1] === arr2[p2]) {
      answer.push(arr1[p1]);
      p1++;
      p2++;
    } else if (arr1[p1] < arr2[p2]) {
      p1++;
    } else {
      p2++;
    }
  }

  return answer;
}

위 코드처럼, 두 포인터가 각기 다른 배열의 시작점에서 출발해서 끝까지 움직이면서 조건에 맞춰서 두 포인터를 동시에 또는 별도로 이동시키는 방법이 일반적인 투 포인터 알고리즘 접근 방식입니다.

인프런 커뮤니티 질문&답변