[릿코드/js] 다시풀기 137.candy

var candy = function(ratings) {
    //일단 하나씩 할당하고,
    //재귀를 통해 이웃이랑 비교하면서 하나씩 추가하면됨. 와일로도 가능할듯?
    let child = new Array(ratings.length).fill(1);
    while(!is_correct(ratings,child))
    {
    const len = child.length;
    for (let i = 0; i < len; i++)
    {
        if (i - 1 >= 0)
        {
            if (ratings[i - 1] < ratings[i] && child[i - 1] >= child[i]) 
            {
                child[i] = child[i - 1] + 1;
            };
        }
        if (i + 1 <= len)
        {
            if (ratings[i] > ratings[i + 1] && child[i] <= child[i + 1])
            {
                child[i] = child[i + 1] + 1;
            };
        }
    }
    }
    return child.reduce((acc,cur) => acc + cur);
};

let is_correct = function(ratings, child)
{
    const len = child.length;
    for (let i = 0; i < len; i++)
    {
        if (i - 1 >= 0)
        {
            if (ratings[i - 1] < ratings[i] && child[i - 1] >= child[i]) 
            {
                return false;
            };
        }
        if (i + 1 <= len)
        {
            if (ratings[i] > ratings[i + 1] && child[i] <= child[i + 1])
            {
                return false;
            };
        }
    }
    return true;
}

-> 나의 풀이

 

ratings와 child 배열을 두고 child의 배열이 조건에 맞는지 확인하면서 while문을 돌린다. 이 while문 안에서 양쪽 조건을 동시에 확인함.

 

하지만 이렇게 하면 while문을 굉장히 많이 돈다는 단점이 있다.

(시간이 느림. 기본적으로 3중 while문인데다가 안에 조건도 몇개나 있다.)

 

var candy = function(ratings) {
    //일단 하나씩 할당하고,
    //재귀를 통해 이웃이랑 비교하면서 하나씩 추가하면됨. 와일로도 가능할듯?
    let child = new Array(ratings.length).fill(1);

    const len = child.length;
    for (let i = 1; i < len; i++)
    {

        if (ratings[i - 1] < ratings[i]) 
        {
            child[i] = child[i - 1] + 1;
        };
    }
    for(let i = len - 2; i >= 0; i--)
    {
        if (ratings[i] > ratings[i + 1])
        {
            if (child[i] <= child[i + 1]) child[i] = child[i + 1] + 1;
        }
    }
    return child.reduce((acc,cur) => acc + cur);
};

-> 다른 이의 풀이를 참고하여 수정한 풀이

 

일단 for문을 돌려서 왼쪽이랑만 비교하여 child배열을 할당한다.

이후 다시 역방향으로 for문을 돌려서 오른쪽을 비교한다.

(이미 왼쪽은 할당이 되어있는상태임)

오른쪽 ratings보다 더 큰지 확인하고, 더 크다면 child[i]도 오른쪽보다 큰지 확인한다. 그렇다면 바꿀 이유가 없고,

그렇지 않다면 오른쪽것보다 +1을 해서 변경을 해준다. 그러면 오른쪽에서도 맞출 수 있다.

 

내가 걱정됐던건 이렇게 다시바꾸면서 왼쪽이랑 비교한 것이 틀어지지 않느냐 하는것이었는데...

1. 현재 값이 왼쪽보다 작거나 같은 경우에 교체할때.

   오른쪽값+1이 현재값이 됨. (그럼 왼쪽값보다 더 커질 수 있다는 뜻.)

  그럼 그 다음에 비교할때 수정이 됨.

  그 다음 비교에서는 왼쪽값이 더 작으니까 현재값의 +1이 될것임,

2. 현재값이 왼쪽보다 큰 경우에 교체할때.

   -> 문제 없음 ( 더 커지는 거니까.)

var candy = function(ratings) {
    let child = new Array(ratings.length).fill(1);

    const len = child.length;
    for (let i = 1; i < len; i++)
    {

        if (ratings[i - 1] < ratings[i]) 
        {
            child[i] = child[i - 1] + 1;
        };
    }
    for(let i = len - 2; i >= 0; i--)
    {
        if (ratings[i] > ratings[i + 1])
        {
            child[i] = Math.max(child[i], child[i + 1] + 1);
        }
    }
    return child.reduce((acc,cur) => acc + cur);
};

gpt는 이렇게 푸는 것이 좀더 안정적이라고 한다 이유는 사실 잘 모르겠다. (정수만 들어오는 경우에 값은 똑같을것같음.)