Skip to main content

135 - Candy

info
  • 문제 보기: 135 - Candy
  • 소요 시간: 51분
  • 풀이 언어: java
  • 체감 난이도: 3️⃣
  • 리뷰 횟수: ✅

풀이 키워드​

스포주의

그리디


풀이 코드​

info
  • 메모리: 45700 KB
  • 시간: 2 ms
class Solution {
    public int candy(int[] ratings) {
        // check continuous asc/desc rating order
        int n = ratings.length;
        int ans = n;
        int asc[] = new int[n];
        int desc[] = new int[n];

        int v = 0;
        for (int i = 1; i < n; ++i) {
            asc[i-1] = v;
            if (ratings[i-1] < ratings[i]) ++v;
            else v = 0;
        }
        asc[n-1] = v;

        v = 0;
        for (int i = n-1; 0 < i; --i) {
            desc[i] = v;
            if (ratings[i-1] > ratings[i]) ++v;
            else v = 0;
        }
        desc[0] = v;

        for (int i = 0; i < n; ++i) {
            ans += Math.max(asc[i], desc[i]);
        }

        return ans;
    }
}

풀이 해설​

rating이 인접 칸보다 높으면 반드시 사탕을 더 받게끔 하면서

배분된 총 사탕 개수는 최소로 만들어야 하는 문제이다.


이번에도 어김없는 말장난
문제를 잘 읽자

You are giving candies to these children subjected to the following requirements:

Each child must have at least one candy.
Children with a higher rating get more candies than their neighbors.

더 높은 rating일 경우라고 명시했고, 같은 rating에 대해선 아무 언급이 없다.

없으면 뭐다? 해당 제약의 대상이 아니라는 것이다.


🙃 거꾸로 생각해보자​

{1, 5, 7}

만약 값들이 오름차순으로 되어있다면 사탕을 점점 1씩 늘려가며 배분해주면 된다. 아주 EZ하다.

그런데 내림차순은?

{9, 3, 2}

'그냥 연속된 내림차순 구간 길이를 구하면 되지 않나?'라고 생각할 수 있지만,

그렇게 한꺼번에 구하면 다음과 같은 케이스에서 사탕 배분이 까다로워진다.

올라갔다 내려갔다
{1, 2, 3, 2, 1}

이러면 다음 값이 오름차순일 경우, 같을 경우, 내림차순일 경우를 나눠서 i, j 인덱스, 연속 구간 길이, 배분할 사탕 수 등의 여러 상태 변수를 계속 관리해주어야 한다.

하지만 수행 시간 약간만 희생하면 이런 복잡한 상태관리를 안해도 된다.

➡️ 오름차순 기준으로만 정방향 스캔해서 배분한 결과와
⬅️ 오름차순 기준으로만 역방향 스캔해서 배분한 결과를 따로 저장해놓고 둘이 비교하면 되기 때문이다.

기준에 맞지 않는다면 배분할 사탕 수를 0으로 초기화해서 총 배분 수를 최소화하고

마지막엔 동일 인덱스에 대하여 두 배분 결과 중 더 큰 값을 선택한다.
(정방향에서 0인데 역방향은 기준에 해당해서 1일 수 있고 그러니까)

결과적으로 T(3n)=O(n)T(3n) = O(n)의 시간복잡도를 가지게 된다.


꼬다리 처리해주기​

for문 내에서 i번째 칸에 값을 넣어주고 있는데, i가 모든 인덱스를 순회하는 것이 아니므로 순회 후 따로 꼬다리로 남은 인덱스를 처리해주어야 한다.

for (int i = 1; i < n; ++i) { ... }
asc[n-1] = v;

for (int i = n-1; 0 < i; --i) { ... }
desc[0] = v;

물론 순회 끝난 i값을 참조해도 되는데, 이러면 i의 스코프를 밖으로 빼야 하고 조금 덜 직관적인 것 같아 n-1, 0으로 인덱싱했다.


메모​

  • 처음에 또 오름차순 내림차순 연속구간을 한꺼번에 처리하려고 투포인터로 짜다가 2359번의 메모 내용이 떠올라서 해당 방식으로 드리프트했는데 현명한 선택이었음 ㅇㅅㅇb