n^2 배열 자르기 level 2 자바

meluu_·2024년 5월 16일

Level 2

프로그래머스

목록 보기

28/30

🧫 문제 분석

✔️ 출처

n^2 배열 자르기 level 2

📖 문제

nxn크기의 2차원 배열을 i행 i열에 i 값을 넣는다.
123
223
333
이런식으로
그다음 각 행을 모두 이어붙이고 left~right까지만 배열로 반환

🔅 문제 풀이

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

        return answer;
    }
}

1차시도때 2차원 배열 만들고 값을 하나씩 넣은다음 그 중에서 left~right 배열을 반환하려 했으나 보면 알겠지만 n의 값이 최대 10^7이고 right - left 는 10^5 미만이다. 2차원 배열을 만들 경우 n *n 인 10^14크기의 배열을 만들어야하므로 메모리 초과가 뜬다.

무작정 풀게 아니라 우리에게는 아주 좋은 나누기 연산과 나머지 연산이 있다.
굳이 한 배열로 이어붙이는 로직을 짤 필요가 없다는 의미이다.

left ~right까지 반복하게 끔 반복문을 만든 후
left / n 과 left % n 중 가장 큰 값이 처음 i행 i열에 i 값을 넣은 그 값이다.
물론 +1을 해주어야한다. 나는 0행, 0열부터 시작하게끔 설정하였으므로..

입출력 예 1번을 예시로 풀어보면
left=2이고 max(2/3, 2%3) 이면 0, 2이므로 arr[0][2] 의 값이라는 뜻이다.
여기서 우리는 처음 열,행이 0부터 시작이므로 최대값 2에 +1을 해준 3이 left=2에 해당하는 값이다.

처음 시도

class Solution {
    public int[] solution(int n, long left, long right) {
        // 메모리 초과
        int[][] arr = new int[n][n];
        int[] answer = new int[(int)(right-left+1)];
        
        for (int i = 0; i < n; i++) {
            for (int j = 0; j <= i; j++) {
                arr[j][i] = arr[i][j] = i + 1;   
            } 
        }

        for (int index = 0; index <= right - left; index++) {
            answer[index] = arr[(int)(left + index) / n][(int)(left + index) % n];
        }
        
        return answer;
    }
}