HackerRank - Array Manipulation

leehyunjon·2022년 11월 28일
0

Algorithm

목록 보기
134/162

array manipulation : https://www.hackerrank.com/challenges/one-month-preparation-kit-crush/problem?isFullScreen=true&h_l=interview&playlist_slugs%5B%5D=preparation-kits&playlist_slugs%5B%5D=one-month-preparation-kit&playlist_slugs%5B%5D=one-month-week-four


Problem

N의 크기의 배열에 각 a와 b 인덱스 사이에 k의 값을 추가해주고, 겹쳐지는 구간은 k를 다른 k와 합하여 줍니다.
모든 작업을 수행하였다면 모든 구간에서 가장 큰 값을 반환해야합니다.

N = 10
qureis = [[1,5,3],[4,8,7],[6,9,1]]
이 주어졌을때 아래와 같습니다.

    a b k
    1 5 3
    4 8 7
    6 9 1

그리고 각 a와 b사이에 k를 N크기의 배열에 작업을 수행한다면 아래와 같이 됩니다.

index->	 1 2 3  4  5 6 7 8 9 10
		[0,0,0, 0, 0,0,0,0,0, 0]
		[3,3,3, 3, 3,0,0,0,0, 0]
		[3,3,3,10,10,7,7,7,0, 0]
		[3,3,3,10,10,8,8,8,1, 0]

조건

3 <= N <= 10^7
1 <= M(quries.size()) <= 2*10^5
1 <= a <= b <= N
0 <= k <= 10^9


Solve

영어 문제는 이해하는게 참 어려운것 같습니다.

첫번째 풀이에서는 단순 구현을 통해 모든 a와 b 구간에 k를 더하여주었습니다.
조건을 보니 O(NM)으로 시간초과가 발생하였습니다.

M은 필수적으로 발생하므로 a와 b구간에 k를 더해주는 것을 O(1)이나 O(logN)으로 줄여줘야 했습니다.
누적합을 통해 구간의 합을 구해줄 수 있습니다.

a~b까지 k를 모두 더해주는 것이아닌, a와 b+1 구간에만 k의 추가와 삭제를 표시해주면 O(N)으로 구간에서 최대값을 구할 수 있습니다.

N = 5, M = 3
quries = [[1,2,100],[2,5,100],[3,4,100]]
일 때,

arr[1]에 100, arr[2+1]에 -100
arr[2]에 100, arr[5+1]에 -100
arr[3]에 100, arr[4+1]에 -100
을 저장해줍니다. 결과는 아래와 같습니다.

이해가 되지 않는다면, 각 a와 b구간에 k를 모두 적용하였을때는 아래와 같습니다.

동일한 결과를 가지게 됩니다.
누적합을 구하였을때 1부터 5까지 누적합을 구해주고 그 과정에서 발생하는 최대값이 N범위에서 가지는 최대값이게 됩니다.


Code

class Result {

    /*
     * 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
     */

    public static long arrayManipulation(int n, List<List<Integer>> queries) {
    // Write your code here
        long[] arr = new long[n+2];
        long max = 0;
        for(List<Integer> query : queries){
            int a = query.get(0);
            int b = query.get(1);
            int k = query.get(2);
            
            arr[a] += k;
            arr[b+1] -= k;
        }
        
        long prefixSum = 0;
        for(int i=1;i<=n;i++){
            prefixSum += arr[i];
            max = Math.max(max, prefixSum);
        }
        return max;
    }

}

Result


Reference

https://devhoma.tistory.com/150

profile
내 꿈은 좋은 개발자

0개의 댓글