[프로그래머스/Python] 연속 펄스 부분 수열의 합

 

 

문제

문제 설명

 

풀이

 

 

문제를 보면서 연속된 펄스 수열의 합 중 최대를 구하는 문제이므로 부분 합으로 풀 수 있겠다는 생각이 들었다.

주어진 sequence의 길이만큼의 펄스 수열을 곱한 뒤, 첫번째 원소 부터 마지막 원소까지 순차적으로 더해서 리스트에 저장했다.

 

그 후 리스트에 저장된 값 중 최솟값과 최대값을 구해서 maxValue - minValue를 계산했다.

maxValue-minValue가 정답인 이유는 쉽게 생각할 수 있다. (이때 maxValue는 양수, minValue는 음수라 가정)

 

예를 들어 0 < a < b 일 때, [0, a] 구간의 합이 최소이고 [0,b] 구간의 합이 최대라면 [0, b] 구간 합의 입장에서는 구간 합이 음수인 [0, a]를 빼주면 [0, a] 구간합 만큼 더 큰 값을 가질 수 있기 때문이다.

​

[예외]

 

구간 합 리스트가 0부터 시작하면 상관 없지만 만약 sequence의 첫 원소부터 시작한다면 예외처리가 필요하다.

 

1.  maxValue>0, minValue>0 인 경우 => maxValue를 리턴하면 된다. (최소값을 안빼는게 더 큰 수열이 됨)
2. maxValue>0, minValue<0 인 경우 => maxValue - minValue 를 리턴하면 된다.
3. maxValue<0 인 경우 => minValue에 -1을 곱한 값을 리턴하면 된다. (펄스 수열의 시작을 반대로 하면 최솟값이 최댓값이나 마찬가지기 때문이다.)

 

 

Code

 

 

def solution(sequence):
    answer = 0
    length=len(sequence)
    lst=[0]*length
    if length==1:
        return abs(sequence[0])
    lst[0]=sequence[0]
    for i in range(1,length):
        if (i%2):
            lst[i]=lst[i-1]-sequence[i]
        else:
            lst[i]=lst[i-1]+sequence[i]
    minV=min(lst)
    maxV=max(lst)
    if maxV>0:
        if minV<0:
            return maxV-minV
        else:
            return maxV
    else:
        return -minV

 

---

 

머리로는 쉽게 생각 할 수 있는데 말로는 표현하기가 참 어려운거 같다...

의문을 가질 만한 내용도 정리하면 좋겠지만, 오히려 더 헷갈릴 수 있으니 빼는게 좋겠지..?

 

 

프로그래머스