[HackerRank] Array Manipulation 풀이

문제

입력 값은 행렬의 크기(n*m)와, 쿼리(query, 여기서는 db 쿼리가 아니라 "연산"을 의미한다.)들로 이루어져있는데, 쿼리의 의미는 a = 시작 인덱스, b = 종료 인덱스, k = 값이다. 각 쿼리는 시작 인덱스 ~ 종료 인덱스 사이의 배열 요소에 값을 더하는 작업을 수행한다. 모든 작업을 수행하고 배열의 최대 값을 반환하면 된다.

n m
a, b, k
a, b, k
a, b, k
...

www.hackerrank.com/challenges/crush/problem

Array Manipulation | HackerRank

 

풀이 과정

Brute Force 방식으로 풀면 일부 submission에 시간 초과가 발생하고, Prefix sum 개념을 활용하면 전부 해결 가능하다.

1. Brute Force 방식으로 푸는 방법

input:

5 3
1 2 100
2 5 100
3 4 100

위 input으로 실행 과정을 나열해보면 아래와 같이 결과가 나온다.

실행 과정 \ index	1	2	3	4	5	설명
initial array	0	0	0	0	0	초기 배열
query 1	+100	+100				인덱스 1, 2에 100을 더한다.
query 1 결과	100	100	0	0	0
query 2		+100	+100	+100	+100	인덱스 2, 3, 4, 5에 100을 더한다.
query 2 결과	100	200	100	100	100
query 3			+100	+100		인덱스 3, 4에 100을 더한다.
query 3 결과 (최종)	100	200	200	200	200

문제의 답은 배열의 최댓값이므로 200

def arrayManipulation(n, queries):
    diff = [0] * n
    max_val = 0
    for s, e, v in queries:
        for j in range(s - 1, e):
            diff[j] += v
            if max_val < diff[j]:
                max_val = diff[j] 
    return max_val

 

2. Prefix sum 개념을 활용하여 푸는 방법 (Diff)

Prefix sum은 누적 값이라고 하며, 이 문제에서는 값을 하나하나 계산하는 것이 아니라, 변화 값만 저장해놓는 방식으로 이 개념을 활용한다. Prefix sub를 계산하는 공식은 시작 인덱스에 값을 더하고, 종료 인덱스 + 1 에 값을 빼면 된다. 무슨말인지 이해가 잘 안되면 아래 풀이를 자세히 보자! (구글링해서 블로그를 다 들어가봐도 이해하기 어려웠다.)

input:

5 3
1 2 100
2 5 100
3 4 100

 

실행 과정을 나열해보면 아래와 같이 나온다. 종료 인덱스 + 1에 값을 넣어야하기 때문에 배열의 길이가 아까보다 늘어났다.

풀이 과정 \ index	1	2	3	4	5	6	설명
initial array	0	0	0	0	0	0	초기 배열
query 1	+100		-100				인덱스 1에 100을 더하고, 인덱스 2 + 1에 => 인덱스 3에 100을 뺀다.
query 1 결과	100	0	-100	0	0	0
query 2		+100				-100	인덱스 2에 100을 더하고, 인덱스 5 + 1에 => 인덱스 6에 100을 뺀다
query 2 결과	100	100	-100	0	0	-100
query 3			+100		-100		인덱스 3에 100을 더하고, 인덱스 4 + 1에 => 인덱스 5에 100을 뺀다
query 3 결과 (diff)	100	100	0	0	-100	-100

이렇게 계산한 결과로 이제 답을 계산해볼 것이다. 이제부터가 중요하다 😭

이 배열을 (difference를 줄여서) diff 라고 이름을 붙이겠다. diff는 우리가 찾는 배열의 차이 값을 가지고 있다고 했는데, diff를 이용해서 우리가 찾는 최종 결과를 구하려면 이렇게 계산하면 된다.

배열의 첫번째 값은 그대로 대입하고, 그 다음 값 부터는 이전 값에 누적한 결과를 대입하면 된다.

diff	100	+100	+0	+0	-100	-100	이해하기 쉽도록 부호를 추가했다.
	⬇️ 그대로 대입한다	누적 ➡️	누적 ➡️	누적 ➡️	누적 ➡️	누적 ➡️
	100	100+100	100+100+0	100+100+0+0	100+100+0+0 -100	100+100+0+0 -100 -100	어떤 값이 누적된 것인지 이해를 돕기 위한 식이다. 실제로 이렇게 계산하지 않는다.
(최종) (진짜)	100	200	200	200	100	0

(앞서 추가한 배열의 길이를 다시 줄이면) brute force로 계산한 결과와 동일하다! 문제의 답은 배열의 최대값이므로 200

굳이 이렇게 어렵게 계산하는 이유는 위에서 언급한 것도 있고, 소스를 보면 알 수 있지만 계산 속도가 줄어들기 때문이다!

O(N^2) -> O(N)

python3으로 풀었다.

def arrayManipulation(n, queries):
    diff = [0] * (n + 1) # prefix sum
    max_val = 0
    for s, e, v in queries:
        diff[s] += v
        if e + 1 <= n: # check out of index
            diff[e + 1] -= v
    val = diff[0]
    for i in range(1, n + 1):
        val += diff[i]
        if max_val < val:
            max_val = val
    return max_val