[algorithm/ 1,2차원 배열탐색] 격자판 최대합 - 행, 열, 대각선 합 중 큰 값 구하기
문제: 행의 합, 열의 합, 대각선 합중 가장 큰 합 구하기
- 열과 행은 헷갈리는 부분이 있어서 꼭 체크해야한다!
=> 이중배열[행][열] - 1행의 합은? 첫번째 줄 1행 모든 열들의 합 (가로값)
- 1열의 합은? 1열에 있는 모든 행의 합 (세로 값)
--- 1열 2열 3열 4열 5열
1행 [[10, 13, 10, 12, 15], -> 1행의 합 (첫번째 줄 1행 모든 열들의 합인 것이다!)
2행 [12, 39, 30, 23, 11], -> 2열의 합
3행 [11, 25, 50, 53, 15],-> 3열의 합
4행 [19, 27, 29, 37, 27], -> 4열의 합
5행 [19, 13, 30, 13, 19]] -> 5열의 합
ex)
1행 합 = arr[0][0] + arr[0][1] + arr[0][2] ..// 가로합 왼쪽에서 오른쪽값
10 + 13 + 10 + ....
2행 합 = arr[1][0] + arr[1][1] + arr[1][2] ..
1열 합 = arr[0][0] + arr[1][0] + arr[2][0] ..// 세로합 위에서 아래
10 + 12 + 11 + ....
2열 합 = arr[0][1] + arr[1][1] + arr[3][1] ..
풀이
- 이중 for문으로 이중배열의 행(i)과 열(j)을 조회한다.
- sum1에 열의 합을 담고 sum2에 행의 합을 담는다.
- 행과 열이 1줄이 다 더해지고, 다음 행과 열의 합을 담기 위해 sum1과 sum2은 0으로 초기화 시킨다.
- sum1에 행의 값을 더할때 열번호가 +1씩 증가하도록 설정
- sum2에 열의 값을 더할때 행번호가 +1씩 증가하도록 설정
- result 변수에 행과 열의 합 sum1과 sum2 중에 큰 값을 담아준다.
-> result에 담긴값(행,열 중 큰값)과 sum1,sum2 다른 행과 열의 합과 반복비교해서 가장 큰값이 들어오게된다. - 행과 열을 비교했으면, 대각선의 합을 비교한다.
- sum1,sum2를 0으로 초기화 해주고 sum1에는 왼쪽대각선, sum2에는 오른쪽 대각선의 합을 담기로한다.
- sum2의 값은 arr[i][arr.length-i-1]로 설정해주는데, 오른쪽 대각선의 시작 첫행과 마지막 5열이기 때문이다.
-> 시작하는 5열은 배열의 인덱스 4 === 해당 인덱스는 배열의 길이 -1 이기 때문이다. - result(행과 열중 큰값이 담김)와 sum1(왼쪽대각선), sum2(오른쪽대각선)의 값을 비교하여 가장 큰값을 result에 담는다.
- result를 반환한다. (가장 큰값이 담김)
function solution(arr){
let result = 0;
let sum1 = 0;
let sum2 = 0;
for(let i = 0; i < arr.length; i++){
// 1열 1행-> 1열 2행 -> 쭉 더해지도록 초기화를 시켜야한다.
// 한 줄이 다 더해지면 열, 행을 합한 값을 초기화한다.
sum1=sum2=0;
for(let j = 0; j < arr.length; j++){
sum1 += arr[i][j]; // 행을 다 더할때, 열번호가 증가(j) 행번호(i)가 고정
// 행 = arr[0][0] + arr[0][1] + arr[0][2]
sum2 += arr[j][i];
// 열을 다 더할때, 행번호가 증가(j) 열번호(i)가 고정
//열 = arr[0][0] + arr[1][0] + arr[2][0]
}
// 가장 큰 값을 담아준다. (행과 열의 합 중에서!)
result=Math.max(result, sum1, sum2);
}
// 대각선을 구하기 위해 우선 초기화를 시켜준 뒤 시작
sum1=sum2=0;
for(let i=0; i<arr.length; i++){
sum1+=arr[i][i]; // 왼쪽에서 시작하는 대각선
sum2+=arr[i][arr.length-i-1]; // 반대쪽 오른쪽에서 시작하는 대각선
}
// result(행과 열중 큰값이 담김), (대각선1),(대각선2) 중 가장 큰값 골라서
result=Math.max(result, sum1, sum2); // 가장 큰값담기
}
return result; // 155
}
```
let arr=[[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]];
console.log(solution(arr));
Author And Source
이 문제에 관하여([algorithm/ 1,2차원 배열탐색] 격자판 최대합 - 행, 열, 대각선 합 중 큰 값 구하기), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@estell/algorithm-12차원-배열탐색-격자판-최대합-행-열-대각선-합-중-큰-값-구하기저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)