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

문제

---

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

프로그래머스

• 소요 시간 : 30분
• 난이도 : LV 3

나의 풀이

---

 

접근 방법

1. [기존 배열 * 1로 시작하는 펄스배열] , [기존 배열 * -1로 시작하는 펄스배열] 2가지 배열을 만든다.

2. 각 2가지 배열의 누적합 배열을 만든다.

3. 누적합 배열에서 가장 큰 값 - (가장 큰 값 이전에 나온 가장 작은값) 이 정답이다. 

시간복잡도

O(N)

코드

def find_max_sum(arr):
    max_value = max(arr)
    max_value_index = arr.index(max_value)
    min_value = 0
    if max_value_index:
        min_value = min(arr[:max_value_index])    
    return max_value - min_value

def set_presum(arr):
    presum = [0]
    for i in range(1, len(arr)+1):
        presum.append(presum[i-1] + arr[i-1])
    return presum

def solution(sequence):
    answer = 0
    n = len(sequence)
    
    # 2가지 펄스 배열 곱하기 
    perse_1, perse_2 = [], [] 
    
    num = 1 
    for i in range(n):
        perse_1.append(num * sequence[i])
        perse_2.append(-num * sequence[i])
        num *= -1
    
    # 누적합 
    presum_1, presum_2 = set_presum(perse_1), set_presum(perse_2)
    
    # 가장 큰 부분 수열의 합 구하기 
    answer = max(answer, find_max_sum(presum_1), find_max_sum(presum_2))
    return answer

 

결과 : 정답

테스트 1 〉	통과 (0.01ms, 10.1MB)
테스트 2 〉	통과 (0.01ms, 10.3MB)
테스트 3 〉	통과 (0.02ms, 10.2MB)
테스트 4 〉	통과 (0.02ms, 10.2MB)
테스트 5 〉	통과 (0.04ms, 10.3MB)
테스트 6 〉	통과 (0.05ms, 10.3MB)
테스트 7 〉	통과 (0.06ms, 10.2MB)
테스트 8 〉	통과 (0.30ms, 10.3MB)
테스트 9 〉	통과 (0.73ms, 10.4MB)
테스트 10 〉	통과 (3.90ms, 11MB)
테스트 11 〉	통과 (7.00ms, 11.8MB)
테스트 12 〉	통과 (79.32ms, 30.1MB)
테스트 13 〉	통과 (75.23ms, 30MB)
테스트 14 〉	통과 (83.63ms, 30.1MB)
테스트 15 〉	통과 (80.47ms, 30.2MB)
테스트 16 〉	통과 (79.37ms, 33.8MB)
테스트 17 〉	통과 (377.43ms, 110MB)
테스트 18 〉	통과 (426.72ms, 113MB)
테스트 19 〉	통과 (390.73ms, 129MB)
테스트 20 〉	통과 (366.22ms, 129MB)

 

---

다른 사람의 풀이

---

https://velog.io/@jaehyeonkim2358/%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%A8%B8%EC%8A%A4Python-%EC%97%B0%EC%86%8D-%ED%8E%84%EC%8A%A4-%EB%B6%80%EB%B6%84-%EC%88%98%EC%97%B4%EC%9D%98-%ED%95%A9

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

접근 방법

내 방법에서 누적합 배열을 따로 생성하지 않고, 바로바로 계산해주었다. 

시간복잡도

O(N)

코드

from sys import maxsize

INF = maxsize

def solution(sequence):
    answer = -INF
    size = len(sequence)
    s1 = s2 = 0				# 1
    s1_min = s2_min = 0		# 2
    pulse = 1
    
    for i in range(size):
        s1 += sequence[i] * pulse
        s2 += sequence[i] * (-pulse)
        
        # 3
        answer = max(answer, s1-s1_min, s2-s2_min)
        
        # 4
        s1_min = min(s1_min, s1)
        s2_min = min(s2_min, s2)
        
        # 5
        pulse *= -1
    return answer

 

결과 : 정답

테스트 1 〉	통과 (0.01ms, 10.3MB)
테스트 2 〉	통과 (0.01ms, 10.3MB)
테스트 3 〉	통과 (0.02ms, 10.3MB)
테스트 4 〉	통과 (0.02ms, 10.1MB)
테스트 5 〉	통과 (0.03ms, 10.2MB)
테스트 6 〉	통과 (0.03ms, 10MB)
테스트 7 〉	통과 (0.04ms, 10.2MB)
테스트 8 〉	통과 (0.33ms, 10.3MB)
테스트 9 〉	통과 (0.66ms, 10.2MB)
테스트 10 〉	통과 (3.26ms, 10.3MB)
테스트 11 〉	통과 (13.37ms, 10.4MB)
테스트 12 〉	통과 (68.20ms, 13.9MB)
테스트 13 〉	통과 (91.04ms, 14MB)
테스트 14 〉	통과 (79.54ms, 14.3MB)
테스트 15 〉	통과 (66.87ms, 14.3MB)
테스트 16 〉	통과 (72.10ms, 14.2MB)
테스트 17 〉	통과 (352.03ms, 31.1MB)
테스트 18 〉	통과 (329.15ms, 31.3MB)
테스트 19 〉	통과 (342.86ms, 31.6MB)
테스트 20 〉	통과 (392.99ms, 31.6MB)

 

테스트 20의 경우 129MB -> 31MB로 메모리가 많이 줄어들었다. 

다른 사람의 풀이

---

https://school.programmers.co.kr/learn/courses/30/lessons/161988/solution_groups?language=python3

프로그래머스

 

접근 방법

펄스 적용된 sequence에서 구간 [a-b]의 합이 최대가 되는 게 정답이다.

 

시간복잡도

O(N)

코드

def solution(sequence):
    v = [0]
    for i,s in enumerate(sequence): 
        v.append(v[-1] + s * [1,-1][i%2])
    
    return abs(max(v) - min(v))

 

결과 : 정답

테스트 1 〉	통과 (0.01ms, 10.3MB)
테스트 2 〉	통과 (0.01ms, 10.2MB)
테스트 3 〉	통과 (0.01ms, 10.3MB)
테스트 4 〉	통과 (0.02ms, 10.2MB)
테스트 5 〉	통과 (0.02ms, 10.2MB)
테스트 6 〉	통과 (0.03ms, 10.1MB)
테스트 7 〉	통과 (0.02ms, 10.1MB)
테스트 8 〉	통과 (0.20ms, 10.1MB)
테스트 9 〉	통과 (0.45ms, 10.2MB)
테스트 10 〉	통과 (2.16ms, 10.2MB)
테스트 11 〉	통과 (5.76ms, 10.9MB)
테스트 12 〉	통과 (32.76ms, 17.8MB)
테스트 13 〉	통과 (30.04ms, 17.9MB)
테스트 14 〉	통과 (48.43ms, 17.8MB)
테스트 15 〉	통과 (27.23ms, 17.8MB)
테스트 16 〉	통과 (30.00ms, 19MB)
테스트 17 〉	통과 (146.67ms, 50.5MB)
테스트 18 〉	통과 (190.50ms, 52.3MB)
테스트 19 〉	통과 (145.74ms, 58.8MB)
테스트 20 〉	통과 (139.62ms, 58.7MB)

정리

---

다른 사람들의 풀이를 보는 건 언제나 새롭다..