투 포인터 ) 이중 순회가 시간 제한에 걸릴 때 고려해볼 알고리즘

작성일 In Views: Disqus:

코딩테스트에서 배열을 순회해야 할 때, 입력값의 조건이 시간 제한에 걸려 단순 순회가 불가능한 경우가 있습니다. 이 때 고려해야할 알고리즘은 ‘투포인터’ 와 ‘이분 탐색’ 입니다. 이 포스팅은 투포인터 알고리즘을 통해 해당 문제를 해결하는 방법을 다루고 있습니다.

▪︎ 투 포인터 알고리즘 (Two-Pointer)

투 포인터 알고리즘은 주어진 배열에서 각각 다른 원소를 가리키는 2개의 포인터를 조작하면서 원하는 값을 도출할 때까지 탐색하는 알고리즘입니다. 각 포인터들의 위치를 정하고 이동하면서 포인트의 위치를 기록하고 처리합니다.

▫︎ 시간 복잡도

순회마다 항상 두 포인터 중 하나는 1씩 증가합니다. 각 포인터는 최대 N까지 증가할 수 있습니다. 기존 배열의 순회에서는 2중 for문을 통해 두 지점을 특정해야하기 때문에 O(N^2)의 시간 복잡도를 지닌 반면, 투포인터 알고리즘을 사용하게 되면 한번의 단순 순회를 통해 포인트들을 이동하면서 처리하기 때문에 O(N)의 시간 복잡도로 문제를 해결할 수 있습니다.

▪︎ Example of Apply

Untitled

▫︎ 문제 접근

문제 해결을 위한 스텝을 나눠보면 다음과 같습니다.

  1. 공통 원소를 찾는다.
  2. 오름차순으로 출력한다.

1번을 해결하기 위한 가장 쉬운 방법은 두 배열 중 하나를 순회하면서 나머지 배열에 현재 인덱스의 요소들이 있는지 판별하는 것입니다. 이후 판별된 요소들만 오름차순으로 정리하면 다음과 같이 풀이할 수 있습니다.

1
2
3
4
5
6
7
8
9
let arr1 = [1, 3, 9, 5, 2];
let arr2 = [3, 2, 5, 7, 8];
let answer = [];

for (let i = 0; i < arr1.length; i++) {
  if (arr2.includes(arr1[i])) answer.push(arr1[i]);
}

console.log(answer.sort((a, b) => a - b)); // output: [2,3,5]

그러나 입력값을 기준으로 시간 복잡도를 판단해보면 O(N^2)의 시간복잡도를 가진 위 코드는 최악의 경우 10^8 이내의 실행되지 못하는 코드입니다. 따라서 O(N)의 시간 복잡도로 해당 문제를 해결해야 합니다.

▫︎ 투 포인터 알고리즘으로 접근

  1. 주어진 배열들을 정렬한다.
  2. 각 배열의 첫 인덱스 요소를 포인터로 가리킨다. (p1, p2)
  3. p1 인덱스 요소와 p2 인덱스 요소를 비교하며 같다면 answer array에 추가하고 다르다면 p2를 이동한다. 이 때 p2가 p1보다 크다면 p1의 위치를 이동시킨다.

▫︎ 풀이

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
function solution(arr1, arr2) {
  let answer = [];
  let p1 = 0;
  let p2 = 0;

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

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

    if (p1 < p2) {
      p1++;
      p2 = 0;
    }
  }

  return answer;
}