자바 알고리즘 문제 풀이 입문. 섹션2. Array(1, 2차원 배열) : 격자판 최대합

 

https://hyejin.tistory.com/1216

자바 알고리즘 문제 풀이 입문. 섹션2. Array(1, 2차원 배열) : 등수 구하기

-> 이전 문제 풀이 

 

 

 

9. 격자판 최대합 

 

설명

5*5 격자판에 아래롸 같이 숫자가 적혀있습니다.

N*N의 격자판이 주어지면 각 행의 합, 각 열의 합, 두 대각선의 합 중 가 장 큰 합을 출력합니다.

 

입력

첫 줄에 자연수 N이 주어진다.(2<=N<=50)

두 번째 줄부터 N줄에 걸쳐 각 줄에 N개의 자연수가 주어진다. 각 자연수는 100을 넘지 않는다.

 

출력

최대합을 출력합니다.

 

예시 입력 1 

5
10 13 10 12 15
12 39 30 23 11
11 25 50 53 15
19 27 29 37 27
19 13 30 13 19

 

예시 출력 1

155

 

 

문제 풀이 1

public int solution(int n, int[][] num) {
    ArrayList<Integer> tmp = new ArrayList<>();

    int sum3 = 0;
    int sum4 = 0;
    for (int i = 0; i < num.length; i++) {
        int sum = 0;
        int sum2 = 0;
        for (int j = 0; j < num[i].length; j++) {
            sum += num[i][j];
            sum2 += num[j][i];
        }
        sum3 += num[i][i];
        sum4 += num[i][n-1 - i];
        tmp.add(sum);
        tmp.add(sum2);
        tmp.add(sum3);
        tmp.add(sum4);
    }

    return tmp.stream().max(Integer::compareTo).get();
}

👩🏻‍💻 : 이 문제는 각 행의 합, 각 열의 합, 대각선의 합을 각각 구해서 가장 큰 값을 리턴해야 한다. 

2차원 배열이기 때문에 이중 for문을 사용해서 합을 구해야 한다. 

우선, sum1 은 행의 합을 구하기 때문에 num[i][j] 의 합 이고, sum2는 열의 합을 구할 것이기 때문에 num[j][i] 의 합을 구하고 

sum3 은 왼쪽에서 시작하는 대각선의 합이므로 num[i][i]의 합을 구해주고, sum4에는 오른쪽에서 시작하는 대각선의 합이므로 num[i][n-1-i] 의 합을 구해주면 된다. 

 

나는 이 값들을 ArrayList에 담고, 그 다음 stream의 max 메서드를 이용해서 최대값을 구해 리턴했다. 

 

 

 

문제 풀이 2

public int solution2(int n, int[][] arr) {
    int answer = Integer.MIN_VALUE;
    int sum1, sum2;  // sum1 행의 합, sum2 열의 합
    for (int i = 0; i < n; i++) {
        sum1 = sum2 = 0;
        for (int j = 0; j < n; j++) {
            sum1 += arr[i][j];
            sum2 += arr[j][i];
        }
        answer = Math.max(answer, sum1);
        answer = Math.max(answer, sum2);
    }
    sum1 = sum2 = 0;
    for (int i = 0; i < n; i++) {
        sum1 += arr[i][i];
        sum2 += arr[i][n - i - 1];
    }

    answer = Math.max(answer, sum1);
    answer = Math.max(answer, sum2);

    return answer;
}

👾 : 강사님은 더 간단하게? 문제를 풀었다. sum1, sum2 변수 두개만 사용하고 행의 합, 열의 합 / 대각선의 합을 따로 구했다. 

(구하는 방식은 동일하다.) 대신 Math.max를 이용해서 answer에 큰 값을 계속 저장하고 있다가. 마지막에 return 해줬다. 

 

이렇게 하면 나처럼 굳이 arraylist에 값을 담고 max를 구하지 않아도 된다..!