[LeetCode] 2657. Find the Prefix Common Array of Two Arrays

2657. Find the Prefix Common Array of Two Arrays

문제 링크

문제 이해하기 및 풀이

prefix common array라는 단어의 정의 자체가 이해하기 어려웠다.
A와 B의 prefix common array가 배열 C일 때, C[i]는 A와 B 모두에서 인덱스 i이하에 존재하는 숫자들의 개수이다.

예시를 들어보자.
A = [1,3,2,4]이고
B = [3,1,2,4]라고 가정하자.

1. i = 0
   • A의 0번 인덱스까지: 1
   • B의 0번 인덱스까지: 3
   • 공통된 숫자가 없음
   • 따라서 C의 0번 인덱스: 0
2. i = 1
   • A의 1번 인덱스까지: 1, 3
   • B의 1번 인덱스까지: 3, 1
   • 공통된 숫자: 1,3
   • 따라서 C의 1번 인덱스: 2
3. i = 2
   • A의 2번 인덱스: 1, 3, 2
   • B의 2번 인덱스: 3, 1, 2
   • 공통된 숫자: 1, 2, 3
   • 따라서 C의 2번 인덱스: 3
4. i = 3
   • A의 3번 인덱스: 1, 3, 2, 4
   • B의 3번 인덱스: 3, 1, 2, 4
   • 공통된 숫자: 1, 2, 3, 4
   • 따라서 C의 3번 인덱스: 4
     

첫 번째 풀이

A를 순회하며 각각의 숫자가 나타난 횟수를 Map에 저장하고, B를 순회하면서 B의 배열 인자를 key로 가지는 Map의 value를 찾아낸다.

/**
 * @param {number[]} A
 * @param {number[]} B
 * @return {number[]}
 */
 var getOrDefault = (map, key) => {
    const value = map.get(key);
    if(value) {
        return value;
    }

    return 0;
};

var findThePrefixCommonArray = function(A, B) {
    const length = A.length;
    const c = [];
    const aMap = new Map();
    for(let i = 0 ; i < length ; i++) {
        aMap.set(A[i], getOrDefault(aMap, A[i]) + 1);
    }
    let count = 0;
    for(let i = 0 ; i < length ; i++) {
        const value = aMap.get(B[i]);
        if(value > 0) {
            aMap.set(B[i], value - 1);
            count++;
        }
        c.push(count);
    }

    return c;
};

• 이 코드는 틀린 풀이다.
• prefix common array는 배열 인자의 순서는 고려하지 않지만, 배열에 어떤 숫자가 존재해야 하는지는 순서가 고려된다.
• 그래서 항상 최대 개수가 C에 저장될 것이다.

두 번째 풀이

A를 순회하며 B랑 같은 인자가 존재하는지 확인하며 지워주는 방법을 생각했다.

/**
 * @param {number[]} A
 * @param {number[]} B
 * @return {number[]}
 */
 var getOrDefault = (map, key) => {
    const value = map.get(key);
    if(value) {
        return value;
    }

    return 0;
};

var findThePrefixCommonArray = function(A, B) {
    const length = A.length;
    const c = [];
    const aMap = new Map();

    for(let i = 0 ; i < length ; i++) {
        let count = 0;
        aMap.set(A[i], getOrDefault(aMap, A[i]) + 1);
        for(let j = 0 ; j < length ; j++) {
            const value = aMap.get(B[j]);
            if(value > 0) {
                aMap.set(B[j], value - 1);
                count++;
            }
        }
        c.push(count);
    }


    return c;
};

• 이 방법도 틀린 이유가 있다.
• A의 이전 index를 읽을 수 없어 값과 인덱스가 일치하는 경우에만 숫자를 세기 때문이다.

결론

위의 두 방법을 통해 놓쳤던 부분을 생각해보면 순서를 고려하지 않는 자료구조에 A의 배열인자를 차례대로 저장하면서 B를 순회하면 된다.
=> Set을 사용하면 쉽게 해결할 수 있다.

코드

/**
 * @param {number[]} A
 * @param {number[]} B
 * @return {number[]}
 */


var findThePrefixCommonArray = function(A, B) {
    const length = A.length;
    const c = [];
    const set = new Set();

    for(let i = 0 ; i < length ; i++) {
        set.add(A[i]);
        let count = 0;
        for(let j = 0 ; j <= i ; j++) {
            if(set.has(B[j])) count++;
        }
        c.push(count);
    }

    return c;
};