[프로그래머스] Lv.2 n^2 배열 자르기 (2차원 배열 ➡️ 1차원 배열 변환 행열 접근 공식,Java)

 

문제설명

입력 & 출력

 

나의 풀이

import java.util.*;

class Solution {
    public int[] solution(int n, long left, long right) {        
        int size = (int)(right - left + 1);
        int[] answer = new int[size];
        
        
        int idx = 0;
        for(long i = left ; i <= right ; i++){
            int row = (int) (i / n);
            int col = (int) (i % n);
            answer[idx++] = Math.max(row,col) + 1;
        }
        
        return answer;
    }
}

 

이번 문제는 문제 설명에서 친절하게 설명해 주듯이 문제자체는 어렵지 않습니다.

 

그러나 주의해야할 점이 있는데 1 ≤ n ≤ 107 제한사항 때문입니다.

 

만약 n이 크면 배열의 크기가 증가하므로 n이 매우 큰 값이라면 메모리초과가 발생합니다.

 

  int[][] arr = new int[n][n];
        
        for(int i = 0 ; i < n ; i++){
            for(int j = 0 ; j < n ; j++){
                arr[i][j] = Math.max(i,j) + 1;
            }
        }

 

저도 처음에는 위 코드와 같이 전체 2차원 배열을 초기화를 해놓고 진행을 하면 메모리 초과가 발생합니다. 따라서 처음 부터 2차원 배열을 만들지 않고 특정 부분의 배열만 만들어야합니다.

 

풀이 설명을 하자면 특정 부분의 크기만큼 1차원 배열을 만들어줍니다.

 

그리고 문제를 잘 보면 각 열 각 행마다 일정한 규칙이 존재합니다.

1	2	3
2	2	3
3	3	3

 

(행, 열)의 값으로 보면 다음과 같습니다.

• (0,0) ➡️ 1
• (0,1) ➡️ 2
• (1,0) ➡️ 2
• (1,1) ➡️ 2
• (2,0) ➡️ 3
• (2,2) ➡️ 3

즉 (행,열) 값 중 큰 값 +1이 그 행열의 값이 된다는 것을 알 수 있습니다.

 

또한 주어진 2차원 배열을 1차원 배열로 변환할 때, 각 요소의 인덱스 i에 대해 다음과 같이 계산할 수 있습니다:

• 행 번호 (row): i / n
  • i를 전체 열의 개수 n으로 나눈 몫은 행(row) 번호입니다.
• 열 번호 (column): i % n
  • i를 전체 열의 개수 n으로 나눈 나머지는 열(column) 번호입니다.

따라서 원하는 행은 i / n으로 알 수 있고, 열은 i % n이고, 행열의 값을 계산하면 Math.max(행, 열) +1입니다.

 

for문 밖에서 최종 left~right 범위의 값을 저장하기 위한 인덱스 변수 idx를 선언하고 해당 인덱스에 저장을 해주면 완성됩니다.