[투포인터] 공통원소 구하기

자바스크립트 알고리즘 문제풀이 강의를 듣고 정리한 내용입니다.

 

 

 

 

📋 문제

두 개의 배열이 주어지면 주어진 배열들의 공통 원소를 추출하여 오름차순으로 출력한다.

 

 

👉 입력

첫 번째 줄에 첫 번째 배열의 크기 N이 주어진다.

두 번째 줄에 N개의 원소가 주어진다.

세 번째 줄에 두 번째 배열의 크기 M이 주어진다.

네 번째 줄에 M개의 원소가 주어진다.

 

이때 원소는 각 배열에 대해 중복이 없이 주어지며 N과 M은 1 이상 30,000 이하의 수를 가진다.

 

 

👈 출력

두 배열의 공통원소를 오름차순으로 정렬하여 출력한다.

 

 

📝 풀이

 

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

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

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

    return answer;
}

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

 

주어진 배열이 정렬되어 있지 않으므로 투 포인터 알고리즘을 사용하기 위해 먼저 arr1과 arr2를 오름차순으로 정렬한다.

p1, p2를 각 배열의 첫 번째 원소를 가리키도록 한 뒤 각 배열의 길이만큼 while문을 돌린다.

 

while문 안에서 p1이 가리키는 arr1의 원소와 p2가 가리키는 arr2의 원소가 동일하다면 이 원소를 answer에 삽입한 후 p1과 p2가 각 배열의 다음 원소를 가리키도록 증가시킨다.

 

p1이 가리키는 arr1의 원소와 p2가 가리키는 arr2의 원소가 동일하지 않다면 이 두 값을 비교한다.

값을 비교하는 이유는 둘 중 작은 값은 다른 배열에 등장할 여지가 없지만 큰 값은 등장할 여지가 있기 때문이다.

 

값을 비교해 더 작은 원소를 가진 포인터의 값을 증가시킨다.

 

while문의 순회가 끝나 arr1과 arr2 중 하나라도 순회가 끝났다면 다른 값들은 비교할 필요가 없기 때문에 answer를 리턴한다.