서비스기업 알고리즘 기출 문제[dp, 누적 합]

문제 설명

어떤 사람이 자신의 하루가 끝나면 '하루의 행복도'를 0에서 10사이의 점수로 기록했습니다.

어느 날 그동안 기록했던 행복도 점수를 보고, 문득 가장 행복했던 리즈 시절이 언제인지 궁금했습니다.

가장 긴 리즈 시절의 기간을 찾으세요.

리즈 시절 조건

• 행복도가 8 보다 크면 행복한 날로 판단합니다.
• 리즈 시절 기간 중 행복한 날이 행복하지 않은 날보다 많아야 합니다.
• 리즈 시절은 연속된 기간입니다.

예시)

입력: happiness = [9,10,6,0,4,6,10]

출력: 3

설명: 가장 긴 리즈 시절은 [9, 10,6] 입니다. 행복한 날이 2번 있으므로 불행한 날이 하루 있어도 됩니다.

제약사항

• 1 <= happiness.length <= 10000
• 0 <= happiness[i] <= 10

---

1. 나이브한 풀이

시간 복잡도 : n^3

def solution(l):
    maxVal = 0
    for i in range(len(l)):
        for j in range(0,i+1):
            flag1,flag2 = 0,0            
            for k in range(j,i+1):
                if l[k] >10:
                    flag1 +=1
                else:
                    flag2 +=1            
                if flag1 > flag2:
                    maxVal = max(maxVal,k-j+1)
    return maxVal

2. 부분합, 누적합(DP)

시간 복잡도 : n^2

def solution(l):
    prefix_sum = [0] * len(l)
    dp = [0] * len(l)
    happy,unhappy = 0,0    
    for i in range(len(l)):
        if l[i] >8:
            happy +=1
        else:
            unhappy +=1
        prefix_sum[i] =[happy,unhappy]
    prefix_sum = list(map(lambda x : x[0]-x[1],prefix_sum))
    for i ,v in enumerate(prefix_sum):
        dp[i] = i+1 if v>0 else 0    
    for i in range(0,len(l)):
        for j in range(0,i):
            dp[i] = max(i-j,dp[i]) if (prefix_sum[i] - prefix_sum[j] >0) else dp[i]    
    return max(dp

3. 세그먼트트리

TODO