[알고리즘] 2-9 격자판 최대합(인프런 자바(Java) 알고리즘 문제풀이 : 코딩테스트 대비 강의)

인프런의 자바(Java) 알고리즘 문제풀이 : 코딩테스트 대비 강의를 수강하며 간략한 문제 설명, 예습 풀이 코드, 강의에서 설명하는 풀이 코드를 정리하고 있습니다.

• 문제 링크 : https://cote.inflearn.com/contest/10/problem/02-09
• 문제 설명 : n*n 배열이 주어졌을때 각 행의합, 각 행의 열, 두 대각선의 합 중 가장 큰 값 출력

예습 풀이

package inflearn.array;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

//격자판 최대합
public class Main2_9 {

    //내 풀이
    public static int solution(int n, int[][] arr) {
        int max = -1;
        int sum = 0;

        //가로 합
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                sum += arr[i][j];
            }

            if (sum > max) {
                max = sum;
            }

            sum = 0;
        }

        //세로 합
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                sum += arr[j][i];
            }

            if (sum > max) {
                max = sum;
            }

            sum = 0;
        }



        //좌상-우하 대각선 합
        for (int i = 0; i < n; i++) {
            sum += arr[i][i];
        }

        if (sum > max) {
            max = sum;
        }

        sum = 0;


        //우상-좌 대각선 합
        for (int i = 0; i < n; i++) {
            int j = n;
            sum += arr[i][--j];
        }

        if (sum > max) {
            max = sum;
        }

        return max;
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int n = Integer.parseInt(br.readLine());
        int[][] arr = new int[n][n];

        for (int i = 0; i < n; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());

            for (int j = 0; st.hasMoreTokens(); j++) {
                arr[i][j] = Integer.parseInt(st.nextToken());
            }
        }


        System.out.println(solution(n, arr));
    }
}

강의 풀이

• 예습 풀이에서는 가로, 세로, 두 대각선을 각각 따로 반복문을 돌려서 문제를 해결했는데, 강의에서는 가로, 세로를 묶어서 한번, 두 대각선을 묶어서 한번 반복하여 문제를 해결함으로써 반복문의 횟수를 반으로 줄였다.
• 둘 중 큰 값을 판별할 때 Math.max() 메서드를 사용

public static int solution2(int n, int[][] arr) {
    int max = -1;
    int sum1=0, sum2=0;

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            sum1 += arr[i][j]; //가로 합
            sum2 += arr[j][i]; //세로 합
        }

        max = Math.max(Math.max(max, sum1), sum2);
        sum1=sum2=0;
    }

    for (int i = 0; i < n; i++) {
        sum1 += arr[i][i]; //좌상-우하 대각선 합
        sum2 += arr[i][n-1-i]; //우상-좌하 대각선 합
    }

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

    return max;
}