[algorithm/ 1,2차원 배열탐색] 격자판 최대합 - 행, 열, 대각선 합 중 큰 값 구하기

10363 단어 algorithmalgorithm

문제: 행의 합, 열의 합, 대각선 합중 가장 큰 합 구하기

  • 열과 행은 헷갈리는 부분이 있어서 꼭 체크해야한다!
    => 이중배열[행][열]
  • 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] ..


풀이

  1. 이중 for문으로 이중배열의 행(i)과 열(j)을 조회한다.
  2. sum1에 열의 합을 담고 sum2에 행의 합을 담는다.
  3. 행과 열이 1줄이 다 더해지고, 다음 행과 열의 합을 담기 위해 sum1과 sum2은 0으로 초기화 시킨다.
  4. sum1에 행의 값을 더할때 열번호가 +1씩 증가하도록 설정
  5. sum2에 열의 값을 더할때 행번호가 +1씩 증가하도록 설정
  6. result 변수에 행과 열의 합 sum1과 sum2 중에 큰 값을 담아준다.
    -> result에 담긴값(행,열 중 큰값)과 sum1,sum2 다른 행과 열의 합과 반복비교해서 가장 큰값이 들어오게된다.
  7. 행과 열을 비교했으면, 대각선의 합을 비교한다.
  8. sum1,sum2를 0으로 초기화 해주고 sum1에는 왼쪽대각선, sum2에는 오른쪽 대각선의 합을 담기로한다.
  9. sum2의 값은 arr[i][arr.length-i-1]로 설정해주는데, 오른쪽 대각선의 시작 첫행과 마지막 5열이기 때문이다.
    -> 시작하는 5열은 배열의 인덱스 4 === 해당 인덱스는 배열의 길이 -1 이기 때문이다.
  10. result(행과 열중 큰값이 담김)와 sum1(왼쪽대각선), sum2(오른쪽대각선)의 값을 비교하여 가장 큰값을 result에 담는다.
  11. 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));

좋은 웹페이지 즐겨찾기