Candy 문제 Link
https://leetcode.com/problems/candy/ (opens in a new tab)
내 풀이
시간초과로 못 풀었다. 왜 이렇게 풀었는지는 그냥 하나하나 Test Case에 대한 예외처리를 하다보니까 이렇게 됐다. 언제쯤이면 깔끔한 풀이를 제대로 해낼 수 있을까......
class Solution:
def candy(self, ratings: list[int]) -> int:
costs = [1 for _ in range(len(ratings))]
for i in range(len(ratings)):
cur = i
if i != len(ratings) - 1:
for j in range(i + 1, len(ratings)):
# 이전 아이가 점수가 더 높은 경우 멈춤
if ratings[cur] > ratings[j]:
cur = j
row = cur - 1
while ratings[row] > ratings[cur] and row > -1 :
if costs[row] > costs[cur] :
break
costs[row] = costs[cur] + 1
row -= 1
cur -= 1
break
# 같은 점수에 온 경우 멈춤
if ratings[cur] == ratings[j]:
break
if ratings[cur] < ratings[j]:
costs[j] = costs[cur] + 1
cur += 1
return sum(costs)Candy 문제 풀이
양쪽의 아이들보다 숫자가 큰 아이는 사탕을 더 많이 가져가야 한다.
양쪽이라는 말은 앞에서 봐도, 뒤에서 봐도 더 크다는 뜻이다.
이를 이용해서 양쪽 방향에서 한 순회를 하면서 숫자가 더 크면 사탕을 더 많이 주면 된다.
class Solution:
def candy(self, ratings: list[int]) -> int:
N = len(ratings)
nums = [1] * N
for n in range(1, N):
if ratings[n - 1] < ratings[n]:
nums[n] = nums[n - 1] + 1
for n in range(N - 1, 0, -1):
if ratings[n - 1] > ratings[n]:
nums[n - 1] = max(nums[n - 1], nums[n] + 1)
return sum(nums)