(Leet Code JS)Find Original Array From Doubled Array

https://leetcode.com/problems/find-original-array-from-doubled-array/

Find Original Array From Doubled Array - LeetCode

Greedy 알고리즘 적용.

 

changed 배열을 오름차순으로 정렬한 후 순회를 한다.

순회를 하면서 number배열에 changed[i]의 갯수를 카운팅한다.

 

다음 for문으로 다시 changed를 순회한다.

현재 changed[i]의 수와 changed[i] * 2의 수가 number 배열에서 1개 이상일 때 후보군이 된다.

현재 방문한 원소가 후보군에 속한다면 해당 숫자의 카운트를 1개 내려준다.

이후 0인지 아닌지 판별하여 2배에 해당하는 카운팅을 내려준다.

0은 2를 곱해도 0이기 때문에 number[0]이 1개 이상인지 확인한 후, true라면 카운트를 내려주고 answer에 0을 넣어준다.

0이 아닌 숫자는 2를 곱한 수의 개수가 1개 이상인지 확인한 후, true라면 카운트를 내려주고 answer에 해당 수를 넣어준다.

 

리턴값은 answer의 길이 * 2가 changed의 길이와 같으면 answer를, 그렇지 않다면 빈 배열 []을 리턴하면 된다.

const findOriginalArray = (changed) => {
    const length = changed.length;
    const number = Array(100001).fill(0);
    const answer = [];
    
    changed.sort((a, b) => a - b);
    
    for(let i = 0; i < length; i++){
        number[changed[i]]++;
    }
    
    for(let i = 0; i < length; i++){
        if(number[changed[i]] && number[changed[i] * 2]){
            number[changed[i]]--;
            
            if(changed[i]){
                number[changed[i] * 2]--;
                answer.push(changed[i]);
            } else{
                if(number[0]){
                    number[0]--;
                    answer.push(0);
                }
            }
        }
    }
    
    return answer.length * 2 === length ? answer : [];
};