HackerRank - Array Manipulation

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

Array Manipulation | HackerRank

매우 골치를 썩였던 문제입니다.

단순히 풀리나 싶더니 어김없이 Time Limit을 걸어놓았더군요 ㅎㅎ

discussion을 조금 보고서야 풀 수 있었습니다.

 

문제 : 길이가 n이며 원소가 모두 0인 배열 arr이 주어질 때, 주어지는 query에 따라서 arr[a:b]에 k만큼 더한다. query들이 끝나면, 배열 내에서 가장 큰 수를 찾는다.

 

input : n, m, a, b, k

n : array의 길이

m : query의 수

a : 시작 index

b : 끝 index

k : 더하는 수

 

Ex) n = 5, m = 3 a,b,k = [[0, 1, 100], [1, 2, 100], [2, 3, 100]]

 

n= 5이므로 처음 배열의 시작은 

 

[0,0,0,0,0]

1) a = 1, b = 2, k = 100

arr 배열의 1번째 원소부터 2번째 원소까지 k만큼 더합니다.

→ [100, 100, 0, 0, 0]

 

이와 같이 문제를 풀어나가시면 됩니다. 다만 단순히 구현만 해서는 Timeout에 걸릴 수 있으니 주의하세요.

직접 풀어보시길 추천합니다. 저는 방법에 대한 힌트를 얻어서 이미 불가능했습니다..

 

방법 :

0) arr = [0] * (n+1) 

* n+1개를 만드는 이유는 1)번 과정을 보시면 이해할 수 있습니다.

 

1) query가 주어질 때([a,b,k]), a-1번째 원소에 +k를, b번째 원소에 -k를 해줍니다.

 * a와 b의 index는 1부터 시작하기 때문에, a,b가 주어졌을 때 arr[a-1: b] += k를 해줘야 합니다.

 * 여기서 (1)번을 수행하는 이유는, a-1번째 원소부터 b-1번째 원소들의 최대값을 표시한 것입니다. 모두 동일한 값을 더했기 때문에 우리가 구하길 원하는 최댓값을 구하는 방법을 간단히 구현하였습니다.

(arr의 최댓값을 구하는 3번 과정을 보시면 더 잘 이해할 수 있습니다.)

 

2) 1)번이 완료되면, arr에 for loop을 돌리면서 값들을 더해줍니다. 더해주는 과정에서 max가 될 때의 값을 찾아냅니다.

 

max, x = 0

for i in arr:

    x += i

    if(max<x):

        max = x