TIL. 투 포인터 알고리즘 문제풀이

효율성(Two Pointers Algorithm)

투 포인터 알고리즘은 이름에서 알 수 있듯이, 두 개의 포인터를 사용하여 문제를 해결하는 방법이다.
이 알고리즘의 핵심은 두 개의 포인터를 사용하여 배열이나 데이터 구조를 순회하면서, 특정 조건에 따라 포인터들을 움직이고 연산을 수행하는 것이다. 두 포인터가 서로 다른 방식으로 움직이거나 같은 방식으로 움직일 수 있으며, 이는 문제의 특성에 따라 달라진다.

두 배열 합치기

문제 설명

오름차순으로 정렬이 된 두 배열이 주어지면 두 배열을 오름차순으로 합쳐 출력하는 프로그램 을 작성하세요.

▣ 입력설명
첫 번째 줄에 첫 번째 배열의 크기 N(1<=N<=100)이 주어집니다. 두 번째 줄에 N개의 배열 원소가 오름차순으로 주어집니다. 세 번째 줄에 두 번째 배열의 크기 M(1<=M<=100)이 주어집니다. 네 번째 줄에 M개의 배열 원소가 오름차순으로 주어집니다. 각 리스트의 원소는 int형 변수의 크기를 넘지 않습니다.

▣ 출력설명
오름차순으로 정렬된 배열을 출력합니다.

▣ 입출력 예

input	output
3 / [1, 3, 5] / 5 / [2, 3, 6, 7, 9]	[1, 2, 3, 3, 5, 6, 7, 9]
4 / [1, 2, 2, 9] / 5 / [2, 3, 4, 8, 9]	[1, 2, 2, 2, 3, 4, 8, 9, 9]

풀이

const combineTwoArray = (a, b) => {
  const combinedArray = [...a, ...b];
  
  console.log(a, b); // [1, 3, 5] [2, 3, 6, 7, 9]
  return combinedArray.sort();

};

let a = [1, 3, 5];
let b = [2, 3, 6, 7, 9];
console.log(combineTwoArray(a, b));

👉 두 배열 a와 b를 합친 후, sort() 메서드를 사용하여 배열을 정렬하는 방법으로 풀이

• 두 배열을 펼칠 새로운 배열을 만든다.
• 새로운 배열에 받은 두 배열을 조건과 상관없이 차례대로 넣는다.
  → 2중포문이 아닌 다른 방법으로
  → 복사해서 넣기
• 질서없는 새로운 배열을 차례순으로 정렬하는 메서드를 이용한다.

❗️ 이 코드는 작동하지만, sort() 메서드의 시간 복잡도가 O(n log n)이므로 두 배열의 길이가 길어질수록 덜 효율적이다. 🤨

Two Pointers Algorithm을 사용한 접근 방식

이 경우, 각 배열에 하나씩 포인터를 두고, 두 배열을 동시에 순회하면서 더 작은 요소를 결과 배열에 추가한다. 이미 배열이 정렬되어 있기 때문에, 전체 배열을 한 번만 순회하면 된다. 이 방법의 시간 복잡도는 O(n+m)이다.

✍️ solution

function mergeArrays(arr1, arr2) {
  let result = [];
  let i = 0,
    j = 0;

  while (i < arr1.length && j < arr2.length) {
    if (arr1[i] < arr2[j]) {
      result.push(arr1[i++]); // 1)
    } else {
      result.push(arr2[j++]);
    }
  }

  // 나머지 요소 추가
  while (i < arr1.length) {
    result.push(arr1[i++]);
  }

  while (j < arr2.length) {
    result.push(arr2[j++]);
  }

  return result;
}

let a = [1, 3, 5];
let b = [2, 3, 6, 7, 9];

console.log(mergeArrays(a, b));

• 1) arr1[i++] 구문은 JS에서 post-increment 연산자를 사용하는 방식이다. 이것은 두가지 작업을 수행한다.
  1. 현재 i 의 값을 증가시킴
  2. i 의 값을 1만큼 증가시킴
  즉, arr1[i++] 가 실행될 때, arr1[i]의 현재 값을 result 배열에 추가한 후에 i를 1만큼 증가시키는 것이다. 이는 arr1 배열의 다음 원소로 이동하고자 할 때 유용하다. 😀

Two Pointers Algorithm의 장점

효율성

이미 정렬된 배열을 사용하기 때문에, 전체 배열을 한 번만 순회하면 된다. 이는 큰 배열에서 특히 유리하다.

추가 메모리 사용 최소화

새로운 배열 외에 추가적인 메모리를 거의 사용하지 않는다.

👉 즉, 첫 번째 방법으로도 문제 해결은 가능하지만, Two Pointer Algorithm을 사용하면 훨씬 효율적이다. 투 포인터 알고리즘은 이미 정렬된 배열을 사용하여 추가적인 정렬 과정 없이 요소들을 합치는 데에 집중한다. 이것은 특히 큰 데이터 세트를 다룰 때 매우 유리한 접근 방식이라고 한다. 🧐

투포인터 알고리즘의 핵심은 두 개의 포인터를 사용하여 두 배열을 동시에 순회하면서, 각 시점에서 더 작은 값ㅇ르 결과 배열에 추가하는 것이다.

✍️ solution2

function solution(arr1, arr2) {
  let answer = [];
  let n = arr1.length;
  let m = arr2.length;
  let p1 = (p2 = 0);
  while (p1 < n && p2 < m) {
    if (arr1[p1] <= arr2[p2]) answer.push(arr1[p1++]);
    else answer.push(arr2[p2++]);
  }
  while (p1 < n) answer.push(arr1[p1++]);
  while (p2 < m) answer.push(arr2[p2++]);
  return answer;
}

console.log(solution(a, b));

• 두 배열 arr1과 arr2에 대한 포인터 p1과 p2를 0으로 초기화

• while (p1 < n && p2 < m) 루프를 사용하여 두 배열을 동시에 순회한다. 이때, 각 배열의 현재 포인터 위치의 원소를 비교하여 더 작은 값을 결과 배열 answer에 추가한다.
  p1++ 또는 p2++을 사용하여 해당 배열의 다음 원소로 이동한다.

• 두 번째와 세 번째 while 루프는 한 배열의 모든 원소가 결과 배열에 추가된 후, 다른 배열에 남아있는 원소들을 결과 배열에 추가한다.

• solution1과 비슷한 풀이이지만 if (arr1[i] < arr2[j]) 와 (arr1[p1] <= arr2[p2]) 에서의 차이는 뭘까? 🧐
  → 두 배열에 같은 값이 있을 때 어떤 배열의 원소를 먼저 추가할 지에 대한 차이가 있다!
  전자의 경우 arr2의 배열의 원소가 먼저, 후자의 경우 arr1의 배열의 원소가 먼저 추가된다. 😀