HackerRank 2d Array ds

2021-06-21

hackerrank

1. 문제

1.1. Given a 2D Array, :

1 1 1 0 0 0
0 1 0 0 0 0
1 1 1 0 0 0
0 0 0 0 0 0
0 0 0 0 0 0
0 0 0 0 0 0
An hourglass in is a subset of values with indices falling in this pattern in 's graphical representation:

a b c
d
e f g
There are hourglasses in . An hourglass sum is the sum of an hourglass’ values. Calculate the hourglass sum for every hourglass in , then print the maximum hourglass sum. The array will always be .

1.2. Example

-9 -9 -9 1 1 1
0 -9 0 4 3 2
-9 -9 -9 1 2 3
0 0 8 6 6 0
0 0 0 -2 0 0
0 0 1 2 4 0

1.3. The hourglass sums are:

-63, -34, -9, 12,
-10, 0, 28, 23,
-27, -11, -2, 10,
9, 17, 25, 18
The highest hourglass sum is from the hourglass beginning at row , column :

0 4 3
1
8 6 6
Note: If you have already solved the Java domain’s Java 2D Array challenge, you may wish to skip this challenge.

1.4. Function Description

Complete the function hourglassSum in the editor below.

hourglassSum has the following parameter(s):

int arr[6][6]: an array of integers
Returns

int: the maximum hourglass sum

1.5. Input Format

Each of the lines of inputs contains space-separated integers .

1.6. Constraints

-9 <= arr[i][j] <= 9
0 <= i, j <= 5

1.7. Output Format

Print the largest (maximum) hourglass sum found in .

Sample Input

1 1 1 0 0 0
0 1 0 0 0 0
1 1 1 0 0 0
0 0 2 4 4 0
0 0 0 2 0 0
0 0 1 2 4 0

1.8. Sample Output

1.9. Explanation

contains the following hourglasses:

image
The hourglass with the maximum sum () is:

2 4 4
2
1 2 4

1.1. 컴퓨팅적 사고

이번 문제는 2중 배열이 주어졌을때 모래시계의 최댓값을 구하는 문제이다

1
2
3

2 4 4
  2
1 2 4

모래 시계의 형태는 다음과 같다. 맨 처음에 해당 되는 모래시계의 전체의 합을 구하는 문제인줄 알고 오역을 하게 되어서 Failed가 났다.

문제에서 원하는것은 이중배열이 주어질때 만들 수 있는 모든 모래시계의 합중 최댓값을 구하는 문제이다.

내가 생각해낸 방법은 다음과 같다.

행,열의 기준으로 해당되는 모래시계의 형태를 몇번 인덱스까지 갈 수 있을까를 먼저 고민했다.

예를 들어 행 0,1,2 열 0,1,2부터 시작해서 모래시계를 만들 수 있는지를 확인한다고 가정하자. 행의 길이가 6이라고 가정하면 모래 시계의 형태대로 갈 수 있는 값은 행의 길이 - 2 만큼이 가능해진다.
즉, 행 0,1,2의 경우 해당 행에서 4개의 모래시계를 만들 수 있다는것이다.

모래시계 1

0 0 0 0 0 0
0 0 0 0 0 0
0 0 0 0 0 0
0 0 0 0 0 0
0 0 0 0 0 0

모래시계 2

0 0 0 0 0 0
0 0 0 0 0 0
0 0 0 0 0 0
0 0 0 0 0 0
0 0 0 0 0 0

모래시계 3

0 0 0 0 0 0
0 0 0 0 0 0
0 0 0 0 0 0
0 0 0 0 0 0
0 0 0 0 0 0

모래시계 4

0 0 0 0 0 0
0 0 0 0 0 0
0 0 0 0 0 0
0 0 0 0 0 0
0 0 0 0 0 0

이제 이렇게 규칙적으로 모래시계를 만들 수 있다는것을 알게되면 우리가 어디까지 반복문을 돌려야할지 알게 된다.
행의 길이 - 2, 열의 길이 -2까지 이중포문을 돌려서 해당되는 모래 시계를 구해주면 되겠다.

즉 우리가 구해야할 점화식은 다음과 같다.

1
2
3

a(i,j)   a(i,j+1)   a(i,j+2)
   -     a(i+1,j+1)     -
a(i+2,j) a(i+2,j+1) a(i+2,j+2)

이제 이것을 바탕으로 매번 모래시계를 만들 수 있는 경우에서 최댓값을 구해주게 된다. 문제의 제약조건을 살펴보면
-9 <= arr[i][j] <= 9 의 범위를 갖는다. 따라서, 우리가 최댓값을 구해줄때 default로 설정할 값이 -63보다 작은값으로 설정을 해주어야한다. 이것이 무슨말이냐면 모래시계를 구할때 위에 설명한 점화식에서 총 7개의 영역을 가지고 있다. 해당 되는 영역에서 모든 값들이 -9로 주어졌다고 가정을 하자. 그러면 다음과 같아질 것이다.

1
2
3

-9 -9 -9
 X -9  X
-9 -9 -9

따라서, 우리가 기본으로 설정할 값은 7 * -9 = -63의 값보다 작은 값으로 설정을 하면서 최댓값을 구해주면된다.
처음에 아무생각없이 0으로 설정하였다가 다른 테스트케이스에서 걸리는것을 보고 바로 수정을 하였다.

시간복잡도

O(N^2)

1.2. 소스코드

import java.io.*;
import java.math.*;
import java.security.*;
import java.text.*;
import java.util.*;
import java.util.concurrent.*;
import java.util.function.*;
import java.util.regex.*;
import java.util.stream.*;
import static java.util.stream.Collectors.joining;
import static java.util.stream.Collectors.toList;

class Result {

    /*
     * Complete the 'hourglassSum' function below.
     *
     * The function is expected to return an INTEGER.
     * The function accepts 2D_INTEGER_ARRAY arr as parameter.
     */

    public static int hourglassSum(List<List<Integer>> arr) {
        // Write your code here
        // 0 1 2 3 4 5 
        // 0 1 2 3 4 5 
        // 0 1 2 3 4 5 
        // 0 1 2 3 4 5 
        // 0 1 2 3 4 5 
        // 0 1 2 3 4 5 
        
        int answer = -64;
        for(int i=0; i<arr.size()-2; i++){
            for(int j=0; j<arr.get(i).size()-2; j++){
                int sum = 0;
                sum += arr.get(i).get(j) + arr.get(i).get(j+1) + arr.get(i).get(j+2);
                sum += arr.get(i+1).get(j+1);
                sum += arr.get(i+2).get(j) + arr.get(i+2).get(j+1) + arr.get(i+2).get(j+2);
                answer = Math.max(answer, sum);
            }
        }
        return answer;
    }

}

public class Solution {
    public static void main(String[] args) throws IOException {
        BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bufferedWriter = new BufferedWriter(new FileWriter(System.getenv("OUTPUT_PATH")));

        List<List<Integer>> arr = new ArrayList<>();

        IntStream.range(0, 6).forEach(i -> {
            try {
                arr.add(
                    Stream.of(bufferedReader.readLine().replaceAll("\\s+$", "").split(" "))
                        .map(Integer::parseInt)
                        .collect(toList())
                );
            } catch (IOException ex) {
                throw new RuntimeException(ex);
            }
        });

        int result = Result.hourglassSum(arr);

        bufferedWriter.write(String.valueOf(result));
        bufferedWriter.newLine();

        bufferedReader.close();
        bufferedWriter.close();
    }
}

Algorithmhackerrank