[python] HackerRank - Candies

문제

https://www.hackerrank.com/challenges/candies/problem

Candies | HackerRank

---

접근

그리디

 

일단 최소 1개씩은 먹야하니 정답 배열을 길이 n만큼 1로 초기화하고 시작.

1. 첫번째 반복문에서는 인덱스 0 -> n-1 순서로 탐색하면서 오른쪽 친구 점수가 높으면 왼쪽 친구 갯수 + 1로 사탕 개수 더해준다.

이렇게 하고 나면

ex) arr = [1,2,3,4,3,2,1] 일때, ans = [1,2,3,4,1,1,1] 이 된다.

 

왼쪽 친구가 점수가 더 높은 경우도 비교해주려면

2. 두번째 반복문에서 n-1 -> 0 순서로 탐색하면서 왼쪽 친구 점수가 높으면 오른쪽 친구 갯수 + 1 로 사탕 개수를 더해주는데

    이때, and 조건으로 ans[i-1] <= ans[i] 를 추가해서 앞에서 이미 더해준 경우는 pass 해준다.

    ex) 가운데(i=3) 점수가 4인 친구는 처음 반복문에서 이미 4개로 더해줬기 때문에 더해주지 않아도된다.

---

코드

def candies(n, arr):
    ans = [1] * n
    for i in range(n-1):
        if arr[i] < arr[i+1]: 
            ans[i+1] = ans[i]+1

    for i in range(n-1,0,-1):
        if arr[i-1] > arr[i] and ans[i-1] <= ans[i]:
            ans[i-1] = ans[i]+1

    return sum(ans)