서점 소유자가 몇 분의 고객 목록 항목에 대해 상점을 연다고 가정합니다. 1분마다 몇 명의 고객(customers[i])이 매장에 들어오고, 그 고객은 모두 그 시간이 지나면 나옵니다. 몇 분 동안 주인은 심술 궂습니다. 이제 i번째 분에 주인이 심술궂으면 grumpy[i] =1, 그렇지 않으면 grumpy[i] =0입니다. 서점 주인이 심술하면 그 순간의 고객은 불행하고 그렇지 않으면 행복합니다. 서점 주인은 X분 동안 심술을 부리지 않는 방법을 알고 있습니다. 그 기술은 두 번 이상 사용할 수 없습니다. 하루 종일 행복할 수 있는 고객의 최대 수를 찾아야 합니다. 따라서 입력이 고객 =[1,0,1,2,1,1,7,5]이고 grumpy =[0,1,0,1,0,1]이고 X =3인 경우 출력은 주인이 마지막 3분 동안 심술을 부리지 않기 때문입니다. 따라서 행복한 고객의 최대 수는 1 + 1 + 1 + 1 + 7 + 5 =16입니다.
이 문제를 해결하기 위해 다음 단계를 따릅니다. −
-
set i :=0, j :=0, sums :=빈 목록 및 temp :=0
-
동안 j – i + 1
-
grumpy[j]가 1이면 temp :=temp + customers[j]
-
j를 1 증가
-
-
합계 배열에 목록 [temp, i, j] 삽입
-
i와 j를 1 증가
-
동안 j <고객 목록의 길이
-
grumpy[i - 1]가 1이면 temp :=temp – 고객[i - 1]
-
grumpy[j]가 1이면 temp :=temp + customer[j]
-
합계 배열에 목록 [temp, i, j] 삽입
-
i와 j를 1 증가
-
-
sums :=내부 목록의 첫 번째 요소를 기반으로 합계 배열 정렬
-
index1 :=sums에서 마지막 목록의 두 번째 요소, index2 :=sums에서 마지막 목록의 세 번째 요소,
-
범위 index1에서 index2에 있는 i에 대해 grumpy[i] :=0
설정 -
답변 :=0
-
범위 0에서 고객 길이까지의 i에 대해
-
grumpy[i]가 0이면 ans :=as + customers[i]
-
-
반환
이해를 돕기 위해 다음 구현을 살펴보겠습니다. −
예시
class Solution(object): def maxSatisfied(self, customers, grumpy, X): i = 0 j = 0 sums = [] temp = 0 while j-i+1<X: if grumpy[j]: temp+=customers[j] j+=1 sums.append([temp,i,j]) i+=1 j+=1 while j<len(customers): if grumpy[i-1]: temp-=customers[i-1] if grumpy[j]: temp+=customers[j] sums.append([temp,i,j]) i+=1 j+=1 sums =sorted(sums,key = lambda v : v[0]) index1 = sums[-1][1] index2 = sums[-1][2] for i in range(index1,index2+1): grumpy[i] = 0 ans = 0 for i in range(len(customers)): if not grumpy[i]: ans+=customers[i] return ans ob = Solution() print(ob.maxSatisfied([1,0,1,2,1,1,7,5],[0,1,0,1,0,1,0,1],3))
입력
[1,0,1,2,1,1,7,5] [0,1,0,1,0,1,0,1] 3
출력
16