[HackerRank] Array Manipulation

⭐ 나의 풀이

#!/bin/python3

import math
import os
import random
import re
import sys
from array import array

#
# Complete the 'arrayManipulation' function below.
#
# The function is expected to return a LONG_INTEGER.
# The function accepts following parameters:
#  1. INTEGER n
#  2. 2D_INTEGER_ARRAY queries
#

def arrayManipulation(n, queries):
    # Write your code here
    arr = array('i', [0] * (n+1))
    for a, b, k in queries :
        arr[a] += k
        if b + 1 <= n : arr[b+1] -= k
    max_result = 0
    result = 0
    for i in range(1, n+1) :
        result += arr[i]
        if max_result < result :
            max_result = result
    return max_result
    
if __name__ == '__main__':
    fptr = open(os.environ['OUTPUT_PATH'], 'w')

    first_multiple_input = input().rstrip().split()

    n = int(first_multiple_input[0])

    m = int(first_multiple_input[1])

    queries = []

    for _ in range(m):
        queries.append(list(map(int, input().rstrip().split())))

    result = arrayManipulation(n, queries)

    fptr.write(str(result) + '\n')

    fptr.close()

queries의 한 행은 a, b, k로 구성되고, a에서 b까지 k만큼 증가하라는 명령이 담겨있다.

시작 위치 a 인덱스에 k를 더해주고 끝나는 위치 b의 바로 다음에 -k를 한다.(누적합을 할 것이라서)

누적합을 계산하면서 갱신했다.

max를 사용해서 return하면 통과못한다.

if 조건문을 사용해서 갱신하는 게 좋다.

 

테케가 아래와 같을 때 예시 👇

10 4
2 6 8
3 5 7
1 8 1
5 9 15

1. 2에서 6까지 8을 더하기

8

-8

2. 3에서 5까지 7을 더하기

8

7

-7

-8

3. 1에서 8까지 1을 더하기

1

8

7

-7

-8

-1

4. 5에서 9까지 15를 더하기

1

8

7

15

-7

-8

-1

-15

5. 누적합

0

1

9

16

16

31

24

16

16

15

0

31을 반환한다.

 

 

---

문제 출처 👇👇

https://www.hackerrank.com/challenges/crush/problem?isFullScreen=true 

Array Manipulation | HackerRank