[Hacker Rank, 해커랭크] Array Manipulation 문제 및 풀이 ( C# )

문제 링크: 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 out이 걸려버리게 됩니다.

 

완벽히 이 문제를 풀기 위해선 Prefix sum (부분합) 의 알고리즘이 조금 필요 하였습니다.

문제요약

난이도: Hard

 

- n 길이의 배열이 주어지고, input에는 각각 a,b,k 라는 변수가 있습니다.

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

- k: 배열에 더할 수

- a: k가 더해질 시작 인덱스 ( 설명에 나온 index는 1부터 시작함 )

- b: k가 더해질 끝 인덱스

 

- n 길이의 배열에 input의 조건을 모두 적용한 뒤, 결과로 나온 배열의 요소중 가장 큰 수를 출력하면 됩니다.

 

---

Example>

 

- n길이의 배열은 처음에 0으로 초기화 되어있고, 위의 표에서 한 줄씩 배열에 적용합니다.

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

표의 제일 위는 배열의 index이고, 각 줄은 처음 input을 한줄씩 적용한 결과 입니다.

최종적으로 배열의 마지막 줄에서 가장 큰 수를 찾으면 10이기에 10을 출력합니다.

 

 

---

문제 풀이

이 문제를 푸는 방법은 크게 2가지가 있습니다. 

 

1. 무식하게 풀기

2. Prefix Sum(누적합)을 이용하여 풀기

 

1번은 뭐 다들 아시기에 패스 하기로 하구.. ( 큰 수로 넘어가면 무조건 Time out 걸리기 때문에 사실 Fail )

저도 한참 고민하다가 2번 방법을 알게되서 풀었습니다.

 

이 문제를 풀기 위해선 Prefix Sum(누적합)을 선행으로 알고 계셔야 풀기 수월한데요.

용어가 어려워 보이지만 단순히 개념만 보면 정말 쉽습니다!

 

일반 배열	1	3	6	11	9	5	...
누적합배열	1	2	3	5	-2	-4	...

뭔가 일반 숫자 배열과 누적합 배열이 많이 다르죠!?

하지만 일반 배열과 누적합 배열은 서로 변환도 가능한 동일한 배열입니다!

 

자세히 누적합 배열을 보면 이 누적합 배열로 모든 일반 배열 요소를 만들 수 있습니다.

예를 들어, 일반 배열의 3번째 인덱스의 숫자(6) 를 알고싶다면, 누적합 배열에서 그냥 3번째 인덱스까지 합해주시면 됩니다. ( 아래 표 참고 )

일반 배열	1	3	6	11	9	5	...
누적합배열	1	2	3	5	-2	-4	...

---

 

이 성질을 이용하여 이 문제를 풀면 정말 손쉽게 풀리게 됩니다.

 

아까 문제 설명에서 보았던 배열을 가지고 풀이를 해보죠.

< INPUT >

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

< Process > ( 실제 코드라 가정하고 index 0 부터 시작, 그래서 a는 -1하겠음 )

0	1	2	3	4	5	6	7	8	9
0	0	0	0	0	0	0	0	0	0
3	0	0	0	0	-3	0	0	0	0
3	0	0	7	0	0	0	0	-7	0
3	0	0	7	0	-2	0	0	-7	-1
3	3	3	10	10	8	8	8	1	0

( 빨간색 글씨: 부분합 배열 / 파란색 글씨: 일반 배열 ) ( 서로 변환 가능! )

 

누적합 성질의 배열을 이용하면 빨간색 글씨의 배열을 얻을 수 있습니다.

누적합 배열을 누적하며 순회하여 각 위치의 숫자를 알아내고, 최대 숫자를 출력하면 됩니다!

 

실제 코드 구현 올려놓겠습니다~!

 

using System.CodeDom.Compiler;
using System.Collections.Generic;
using System.Collections;
using System.ComponentModel;
using System.Diagnostics.CodeAnalysis;
using System.Globalization;
using System.IO;
using System.Linq;
using System.Reflection;
using System.Runtime.Serialization;
using System.Text.RegularExpressions;
using System.Text;
using System;

class Solution
{

    // Complete the arrayManipulation function below.
    static long arrayManipulation(int n, int[][] queries)
    {
        var arr = new long[n + 1];
        for (var i = 0; i < queries.Length; ++i)
        {
            // add
            var add = queries[i][2];

            // first idx
            arr[queries[i][0] - 1] += add;
            // Last idx
            arr[queries[i][1]] -= add;
        }

        // Find Max
        var max = long.MinValue;
        var sum = 0L;
        for (var i = 0; i < arr.Length; ++i)
        {
            sum += arr[i];
            max = Math.Max(max, sum);
        }

        return max;
    }

    static void Main(string[] args)
    {
        TextWriter textWriter = new StreamWriter(@System.Environment.GetEnvironmentVariable("OUTPUT_PATH"), true);

        string[] nm = Console.ReadLine().Split(' ');

        int n = Convert.ToInt32(nm[0]);

        int m = Convert.ToInt32(nm[1]);

        int[][] queries = new int[m][];

        for (int i = 0; i < m; i++)
        {
            queries[i] = Array.ConvertAll(Console.ReadLine().Split(' '), queriesTemp => Convert.ToInt32(queriesTemp));
        }

        long result = arrayManipulation(n, queries);

        Console.
        textWriter.WriteLine(result);

        textWriter.Flush();
        textWriter.Close();
    }
}