[Array/String][Hard] 135. Candy

https://leetcode.com/problems/candy/description

 

Q. 주어진 정수 배열 ratings는 아이들의 사탕에 대한 평점을 의미한다. 

 이때, 모든 아이들이 사탕 1개 이상씩 갖게 한다. 

 다만, 바로 주변 보다 평점이 높은 아이는 해당 낮은 주변 아이보다 더 많이 사탕을 갖게 한다. 

 최소로 필요한 사탕의 수를 찾아라.

 

 

Solution

 우선 정확하게 문제 해석을 해 본다. 

 

 모든 아이들은 우선 1개 이상의 사탕을 갖는다. 

 주변보다 평점이 높다면, 주변보다 사탕도 많아야 한다. 

 

 예를 들어 평점이 1,3,4,5,2  라면, 

 

 1, 2, 3, 4, 1 

 의 사탕을 주어야 조건을 만족하게 된다. 

 

 2, 0, 3, 3, 2 의 평점이 주어진 다면, 

 2, 1, 2, 2, 1 의 사탕을 가져야 한다. 

 

2, 0, 3, 4, 2 의 평점이 주어진 다면, 

2, 1, 2, 3, 1 의 사탕을 가져야 한다. 

 

즉, rating[a] > rating[a-1] && rating[a] > rating[a+1] 일 때 candy값이 주변보다 더 크면 되는 것이다. 

다만, 이때 문제는, candy값이 특정 index를 처리할때, 한쪽 방향만 확정적 이라는 것이다,

즉, left to right로 candy수를 주면, a-1 은 candy수가 확정되었으나, a+1은 아직 정해지기 이전이라는 것이다. 

 

 

따라서 위 연산을 양방향에 대해 수행하고, 

더 큰 값을 취한 후 이를 최종 계산에 사용한다.

 

이를 로직으로 써 본다. 

 

public int Candy(int[] ratings) 
{
    List<int> candy = new List<int>();
    List<int> candyR = new List<int>();
    for(int q = 0; q < ratings.Length; ++q)
    {
        candy.Add(1);
        candyR.Add(1);
    }

    for(int q = 1; q < candy.Count; ++q)
    {
        if(ratings[q] > ratings[q-1])
            candy[q] = candy[q-1] + 1;
    }
    for(int q = candy.Count-2; q >= 0; --q)
    {
        if(ratings[q] > ratings[q+1])
            candyR[q] = candyR[q+1] + 1;
    }

    int ret = 0;
    for(int q = 0; q < candy.Count; ++q)
    {
        ret += Math.Max(candy[q], candyR[q]);
    }
    return ret;
}

 

적절한 결과.

 

노트 : 문제 해석이 매우  중요한 문제.