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

문제 이해하기

부분 펄스가 있는데 해당 부분 펄스를 적용하고 나서 가장 큰 합을 가지는 부분 수열의 값을 찾는 문제였다.

 

https://school.programmers.co.kr/learn/courses/30/lessons/161988

프로그래머스

 

문제 해결 방법 설명하기

 

1. 가장 큰 부분 수열이 되려면?

가장 큰 부분 수열을 찾기 위해서 크게 두 가지 방법이 있다. 하나는 이중 for문을 이용해서 가장 큰 값을 갖는 부분 수열을 찾을 수 있을 것이다. 하지만 sequence 배열의 길이를 보면 해당 방법은 불가능하다.

 

따라서 연속된 부분 수열의 값이 최대값이 되는 조건을 생각했다. 예를 들어, 다음과 같은 수열 (1, 2, 3, -10, 20, 1)이 있다고 가정하자. 1, 2, 3까지는 모두 더하는 것이 합이 더 커지기 때문에 더하는 것이 맞다. 마찬가지로 -10도 더하는 것이 맞다. 이전 값과 현재 값을 더하는 것이 현재 값부터 시작하는 것보다 크기 때문이다.

 

그러나 20에 대해서는 -4와 더하는 것이 옳지 않다. 왜냐하면 "이전 값 + 현재 값 = 16"이지만 해당 구간을 처음 시작점으로 잡으면 20이 되기 때문에 이전의 합들은 필요하지 않게 된다.

 

위의 생각을 구현하면 아래의 코드와 같고, 이는 O(N) 시간 복잡도를 갖으며 문제를 충분히 해결할 수 있다.

 

 

그렇다면 20도 -4랑 더해주는 것이 옿은지를 생각해보면 당연히 옳지 않다. 왜냐하면  "이전 값 + 현재값 = 16"이지만 해당 구간을 처음 시작점으로 잡으면 20이기 때문에 이전의 합들은 필요없게 된다.

 

위의 생각을 구현하면 아래의 코드와 같고 O(N)임으로 문제를 충분히 해결할 수 있게 된다.

    cache = [plus_alpha[0]]
    for i in range(1, len(plus_alpha)):
        if  (plus_alpha[i] < cache[i-1] + plus_alpha[i]):
            cache.append(cache[i-1] + plus_alpha[i])
        else:
            cache.append(plus_alpha[i])
    answer = max(answer, max(cache))

 

2. 부분 펄스는 어떻게 줄 것이가

부분 펄스를 적용하기 위해서는 처음부터 [1, -1...]과 [-1, 1...]로 시작하는 부분 배열을 sequence 배열에 적용해주면 모든 부분 배열에 부분 펄스를 적용한 효과를 얻을 수 있다.

 

    pattern = [1 if i % 2 == 0 else -1 for i in range(len(sequence))]
    plus_alpha = [i*j for i, j in zip(sequence, pattern)]
    pattern = [-1 if i % 2 == 0 else 1 for i in range(len(sequence))]
    minus_alpha = [i*j for i, j in zip(sequence, pattern)]

 

코드

def solution(sequence):
    answer = 0
    
    pattern = [1 if i % 2 == 0 else -1 for i in range(len(sequence))]
    plus_alpha = [i*j for i, j in zip(sequence, pattern)]
    pattern = [-1 if i % 2 == 0 else 1 for i in range(len(sequence))]
    minus_alpha = [i*j for i, j in zip(sequence, pattern)]  
    
    
    cache = [plus_alpha[0]]
    for i in range(1, len(plus_alpha)):
        if  (plus_alpha[i] < cache[i-1] + plus_alpha[i]):
            cache.append(cache[i-1] + plus_alpha[i])
        else:
            cache.append(plus_alpha[i])
    answer = max(answer, max(cache))
    
    cache = [minus_alpha[0]]
    for i in range(1, len(minus_alpha)):
        if  (minus_alpha[i] < cache[i-1] + minus_alpha[i]):
            cache.append(cache[i-1] + minus_alpha[i])
        else:
            cache.append(minus_alpha[i])
            
    answer = max(answer, max(cache))
    
    
    return answer

if __name__ == "__main__":
    sequence = [2 ,3 -6, 1, 3 -1, 2, 4]
    print(solution(sequence))  # 10

코드 리뷰

#누적합을 이용한 풀이법
def solution(sequence):

    # 1 부터 연속펄스 부분 수열을 곱한값 찾기 prefix sum 만들기 
    # maxV - minV 
    # 각각의 리스트에서 max()
    answer = 0
    prefixS = [0]
    for i in range(len(sequence)):
        pulse = 1 if i%2 ==0  else -1
        prefixS.append(prefixS[-1]+pulse*sequence[i])


    return abs(max(prefixS) - min(prefixS))

배운점 정리하기

처음에 나도 누적합을 생각했는데 연속된 부분의 max값을 찾으려면 N2의 연산시간이 필요하다고 생각했다.

하지만 코드리뷰에서 나온 방식이 있는데 상당히 대단하다.