geeksforgeeks contribute 하기

개발👩‍💻/기타

geeksforgeeks contribute 하기

gigibean 2022. 9. 17. 23:49

728x90

🔒 문제

geeksforgeeks 사이트에서 그리디 알고리즘 관련 아티클을 읽다가 뭔가 이상한 부분을 발견했다.

https://www.geeksforgeeks.org/minimum-product-subset-array/

Minimum product subset of an array - GeeksforGeeks

A Computer Science portal for geeks. It contains well written, well thought and well explained computer science and programming articles, quizzes and practice/competitive programming/company interview Questions.

www.geeksforgeeks.org

위 링크의 JS Implementation 부분 코드이다.

<script>
 
// Javascript program to find maximum
// product of a subset.
function minProductSubset(a, n)
{
    if (n == 1)
        return a[0];

    let negmax = Number.MIN_VALUE;
    let posmin = Number.MIN_VALUE;
    let count_neg = 0, count_zero = 0;
    let product = 1;
 
    for(let i = 0; i < n; i++)
    {
         
        // If number is zero, count it
        // but dont multiply
        if (a[i] == 0)
        {
            count_zero++;
            continue;
        }
 
        // Count the negative numbers
        // and find the max negative number
        if (a[i] < 0)
        {
            count_neg++;
            negmax = Math.max(negmax, a[i]);
        }
 
        // Find the minimum positive number
        if (a[i] > 0 && a[i] < posmin)
        {
            posmin = a[i];
        }
 
        product *= a[i];
    }
 
    // If there are all zeroes
    // or zero is present but no
    // negative number is present
    if (count_zero == n || (count_neg == 0 &&
        count_zero > 0))
        return 0;
 
    // If there are all positive
    if (count_neg == 0)
        return posmin;
 
    // If there are even number except
    // zero of negative numbers
    if (count_neg % 2 == 0 && count_neg != 0)
    {
 
        // Otherwise result is product of
        // all non-zeros divided by maximum
        // valued negative.
        product = parseInt(product / negmax, 10);
    }
    return product;
}
 
// Driver code
let a = [ -1, -1, -2, 4, 3 ];
let n = 5;
 
document.write(minProductSubset(a, n));
 
</script>

여기에서 이상한 부분이 있었다.

let negmax = Number.MIN_VALUE;
let posmin = Number.MIN_VALUE;

위와 같이 가장 큰 음수와 가장 작은 양수를 찾기위한 변수를 초기화 하는 부분이었는데,

...
if (a[i] < 0)
{
    count_neg++;
    negmax = Math.max(negmax, a[i]); // 여기
}

// Find the minimum positive number
if (a[i] > 0 && a[i] < posmin)
{
    posmin = a[i]; // 여기
} 

...

표시된 부분에서 사용하는 것이기 때문에 예제에서는 사용되지 않는 값이지만,

(예제에서는 postmin과 nexmax 값을 사용하지 않는 [-1, -1, -2, 4, 3] 이라는 값을 사용하기 때문에)

다른 예제를 넣어보면 원치않는 값이 나올 것이다.

왜냐하면,

가장 큰 음수를 찾기 위해서는 음수끼리 비교해야 원하는 값을 도출할 수 있고,

가장 작은 양수를 찾기 위해서는 앞에 수보다 작은 수를 찾아야 하기 때문이다.

그러나 Number.MIN_VALUE로 두 개의 변수를 초기화 한다면 둘다 어떤 값이 들어와도 초기값을 리턴하게 된다.

Number.MIN_VALUE는 자바스크립트에서 양수 중 가장 작은 값을 나타낸다.

그 말은 즉슨,

negmax에서 Number.MIN_VALUE와 어떠한 음수를 비교해도 Number.MIN_VALUE가 가장 크며,

posmin에서 Number.MIN_VALUE와 어떠한 양수를 비교해도 Number.MIN_VALUE가 가장 작는 것을 의미한다.

이를 제대로 동작하게 하기 위해서는 아래와 같이 수정해주어야 한다.

negmax = Number.NEGATIVE_INFINITY

posmin = Number.MAX_VALUE

수정된 코드 🧩

<script>
 
// Javascript program to find maximum
// product of a subset.
function minProductSubset(a, n)
{
    if (n == 1)
        return a[0];
 
    // Find count of negative numbers,
    // count of zeros, maximum valued
    // negative number, minimum valued
    // positive number and product of
    // non-zero numbers
    let negmax = Number.MAX_VALUE;
    let posmin = Number.NEGATIVE_INFINITY;
    let count_neg = 0, count_zero = 0;
    let product = 1;
 
    for(let i = 0; i < n; i++)
    {
         
        // If number is zero, count it
        // but dont multiply
        if (a[i] == 0)
        {
            count_zero++;
            continue;
        }
 
        // Count the negative numbers
        // and find the max negative number
        if (a[i] < 0)
        {
            count_neg++;
            negmax = Math.max(negmax, a[i]);
        }
 
        // Find the minimum positive number
        if (a[i] > 0 && a[i] < posmin)
        {
            posmin = a[i];
        }
 
        product *= a[i];
    }
 
    // If there are all zeroes
    // or zero is present but no
    // negative number is present
    if (count_zero == n || (count_neg == 0 &&
        count_zero > 0))
        return 0;
 
    // If there are all positive
    if (count_neg == 0)
        return posmin;
 
    // If there are even number except
    // zero of negative numbers
    if (count_neg % 2 == 0 && count_neg != 0)
    {
 
        // Otherwise result is product of
        // all non-zeros divided by maximum
        // valued negative.
        product = parseInt(product / negmax, 10);
    }
    return product;
}
 
// Driver code
let a = [ -1, -1, -2, 4, 3 ];
let n = 5;
 
document.write(minProductSubset(a, n));
 
</script>