<Hard> Candy (LeetCode : C#)

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

📕 문제 설명

n명의 아이들이 각자 rating을 가지고 있을 때 다음의 조건을 만족시키면서 아이들에게 나눠줄 최소 사탕 개수 반환하기

1) 아이들은 최소 1개의 사탕을 받아야한다.
2) 더 높은 rating을 가진 아이는 주변의 아이보다 더 많은 사탕을 받아야한다.

• Input
  rating 배열 (int[])
• Output
  최소 사탕 개수 (int)

예제

풀이

왼쪽 -> 오른쪽, 오른쪽 -> 왼쪽으로 다음의 로직을 적용해 사탕 수를 저장한 다음 더 큰걸로 최종 답 결정
1) 왼쪽 -> 오른쪽 : 이전 것보다 rating 더 크면 이전 candy 수 + 1, 아니면 1로 초기화
2) 오른쪽 -> 왼쪽 : 뒤에거 보다 rating 더 크면 뒤의 candy 수 + 1, 아니면 1로 초기화

public class Solution {
    public int Candy(int[] ratings) {
        if (ratings.Length == 1) return 1;

        int n = ratings.Length;
        int[] leftDp = new int[n];
        int[] rightDp = new int[n];
        
        leftDp[0] = 1;
        // 왼쪽에서 오른쪽 돌면서 사탕 수 갱신
        for (int i = 1; i < ratings.Length; i++)
        {
            int prevRating = ratings[i - 1];
            if (ratings[i] <= prevRating)
            {
                leftDp[i] = 1;
            }
            else
            {
                leftDp[i] = leftDp[i - 1] + 1;
            }
        }
        // 오른쪽에서 왼쪽 돌면서 사탕 수 갱신
        rightDp[n - 1] = 1;
        for (int i = ratings.Length - 2; i >= 0; i--)
        {
            int nextRating = ratings[i + 1];
            if (ratings[i] <= nextRating)
            {
                rightDp[i] = 1;
            }
            else
            {
                rightDp[i] = rightDp[i + 1] + 1;
            }
        }
        // 왼쪽, 오른쪽 중 최대 값 가져오기
        int answer = 0;
        for (int i = 0; i < n; i++)
        {
            answer += Math.Max(leftDp[i], rightDp[i]);
        }

        return answer;
    }
}

결과