[LeetCode 풀이/python] 135. Candy (hard)

문제 설명: 일렬로 줄 서있는 n 명의 어린이가 있다. 이들 각 어린이가 받은 점수는 정수 배열 ratings 에 저장되어 있다. 너는 다음과 같은 요구 조건을 만족하도록 이들 어린이에게 사탕을 주어야 한다: 

• 각 어린이는 최소 하나의 사탕을 가진다
• 더 높은 점수를 받은 어린이는 이웃한 어린이보다 더 많은 사탕을 가진다

이들 어린이에게 사탕을 나눠주기 위해 필요한 사탕의 최소 개수를 리턴하시오.

 

(There are n children standing in a line. Each child is assigned a rating value given in the integer array ratings.

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.

Return the minimum number of candies you need to have to distribute the candies to the children.)

 

 

예시 1)

입력: ratings = [1,0,2]  -->  출력: 5

설명: 첫번째, 두번째, 세번째 어린이에게 각각 2, 1, 2 개의 사탕을 주면 된다!

 

예시 2)

입력: ratings = [1,2,2]  -->  출력: 4

설명: 1, 2, 3 번째 어린이에게 각각 1, 2, 1 개 사탕을 준다. 세번째 어린이에게 1개의 사탕을 주어도 위의 두 조건을 만족한다는 점...!

 

제한 조건:

• n == ratings.length
• 1 <= n <= 2 * 10^4
• 1 <= ratings[i] <= 2 * 10^4

 

------ * ------ * ------ * ------

 

[풀이 1안] -- not a solution!

• 접근법
  • 모든 어린이에게 최소 1개의 사탕을 주어야 하므로, 일단 첫번째 어린이에게 하나의 사탕을 주고 이를 기준으로 ratings[i] 값에 따라 사탕의 개수를 조정해나감
  • 바로 직전에 사탕을 받은 어린이보다 현재 순서의 어린이가 점수가 높으면 이전 어린이보다 사탕을 하나 더 주고, 만약 둘의 점수가 같다면 현재 어린이는 1개의 사탕을 줌 (점수가 같다고 굳이 동일한 수의 사탕을 줄 필요가 없다..!)
  • 만약 직전 어린이보다 점수가 현재 어린이의 점수가 낮은 경우, 현재 어린이에게 최소 1개의 사탕을 주었을 때 이전 어린이와 사탕 개수의 차이가 나지 않는다면 이전 어린이에게 하나를 더 준다
    • 연쇄적으로, 점수가 더 높으나 사탕 개수가 차이나지 않는 경우가 발생할 수 있으므로 while 문을 돌며 역추적(...) 하여 추가 사탕을 준다

 

• 코드 구현

def candy(ratings: List[int]) -> int:
    res = [0]*len(ratings)
    res[0] = 1
        
    for i in range(1, len(ratings)):
        if ratings[i-1] == ratings[i]:
            res[i] = 1
                
        elif ratings[i-1] > ratings[i]:
            res[i] = 1
            while (ratings[i-1] > ratings[i]) and (res[i-1] == res[i]):
                res[i-1] += 1
                i -= 1
                
        else:
            res[i] = res[i-1]+1

    return sum(res)

 

• 결과
  • 기본적으로 배열 ratings 을 선형적으로 탐색하면서, 중간에 조건에 따라 while 문을 다시 선형적으로 돌게 되므로 결과적으로 O(n^2) 이 되어 비효율적인 코드가 됨 ㅠㅠ
  • Time Limit Exceed Error 로 인해 통과하지 못함 ㅜㅜ

 

 

[풀이 2안]

• 접근법
  • 일단 배열의 앞에서 뒤로 선형적으로 탐색하며, 이전 어린이보다 더 점수가 높은 어린이에게는 사탕을 하나 더 주는 조건을 만족하게 함
  • 이전 풀이에서 for 문 안에 while 문을 돌렸던 것을 분해...!
    • 1차로 앞->뒤 탐색을 거친 결과에 대해 반대로 뒤->앞 탐색을 진행하여 이웃한 어린이보다 더 점수가 높으나 더 많은 사탕을 받지 못한 경우에 대해 보완해 줌! 

 

• 코드 구현

def candy(ratings):
    res = [1]*len(ratings)
    lbase = rbase = 1
        
    # front to back
    for i in range(1, len(ratings)):
        lbase = lbase + 1 if ratings[i] > ratings[i-1] else 1
        res[i] = lbase
            
    # back to front
    for i in reversed(range(0, len(ratings)-1)):
        rbase = rbase + 1 if ratings[i] > ratings[i+1] else 1
        res[i] = max(rbase, res[i])
                    
    return sum(res)

 

• 결과
  • 배열의 선형 탐색을 2번 반복하므로 O(2*n) = O(n) 의 시간 복잡도를 가짐!
  • loop 문을 이중으로 쓰지 않고 분해(..!) 하는 접근법 잘 익혀두자 ~_~