[HackerRank] ArrayManipulation #Python

www.hackerrank.com/challenges/crush/problem?h_l=interview&playlist_slugs%5B%5D=interview-preparation-kit&playlist_slugs%5B%5D=arrays

Array Manipulation | HackerRank

코드 1

def arrayManipulation(n, queries):
    indices = [0] * (n+1)
    max_val = 0
    
    for start, end, value in queries:
        for i in range(start, end+1):
            indices[i] += value
            max_val = max(max_val, indices[i])
            
    return max_val

직접 배열을 생성하여 하나하나 더 해주니 아니나다를까, 시간초과가 났다.

 

코드 2

def arrayManipulation(n, queries):
    indices = [0] * (n + 1)
    max_value, sum_value = 0, 0
    for start, end, value in queries:
        indices[start] += value
        if end + 1 <= n:
            indices[end + 1] -= value
   
     for index_value in indices:
        sum_value += index_value
        max_value = max(max_value, sum_value)
     
     return max_value

1. 인덱스 리스트를 만들어(indices) 처음(start)에 +value을 해주고 그 구간이 끝나는 끝부분(end + 1) 에 -value

2. start와 end 모두 구간에 포함이므로 순차적 덧셈에 end구간도 포함되게 하려면 end + 1부분에서 더해준 값을 빼주어야한다.

3. 인덱스 배열(indices)를 순차적으로 더해주며 max_value값을 갱신