[프로그래머스/JAVA] n^2 배열 자르기

https://school.programmers.co.kr/learn/courses/30/lessons/87390

프로그래머스

 

---

[ 오답 노트 ]

❌ 기존 오답 코드

class Solution {
    public int[] solution(int n, long left, long right) {
        int[] answer = new int[right - left + 1];
        // 1. n행 n열 크기의 2차원 배열 만들기
        // n = 3 (3행 3열)일때,
        // 1 2 3
        // 2 2 3
        // 3 3 3
        
        // 2. 1행, 2행,... n행 잘라내어 모두 이어붙인 새로운 1차원 배열 만들기
        // 1 2 3 / 2 2 3 / 3 3 3
        
        // 3. arr[left], arr[left+1]...arr[right]만 남기고 나머지 지우기
        // arr[2], arr[3], arr[4], arr[5]일때,
        // 답은 [3,2,2,3]
        //-----------------------
        
        // 1. n행 n열 크기의 2차원 배열 만들기
        // [[1,2,3], [2,2,3], [3,3,3]]
        //  i j = 0   1    2
        //  0   i+1, i+2, i+3,    
        //  1   i+2, i+2, i+3,
        //  2   i+3, i+3, i+3
        // [0,0] = 1
        // [0,1], [1,0], [1,1] = 2
        // [0,2], [1,2], [2,0],[2,1],[2,2] = 3
        int arr[][] = new int[n][n]; 
        for(int i = 0; i < n; i++) {
            for(int j = i; j < n; j++) {
                if(i >= j) {
                    arr[i][j] = i+1;
                }else if(i <= j) {
                    arr[i][j] = j+1;
                }// [[1,2,3], [2,2,3], [3,3,3]]
                
                // -> [1,2,3,2,2,3,3,3,3]으로 1차원 배열로 바꾸기
                int arr2[] = new int[n*n];
                for(int z = 0; z < n*n; z++) {
                    arr2[z] = arr[i][j];
                }
                
                // 2.arr2[left], arr2[left+1]...arr2[right]만 남기고 나머지 지우기
                // arr2[2], arr2[3], arr2[4], arr2[5]
                for(int t = left; t < right; t++) {
                    answer[t] = arr2[t];
                }
            }
        } 
    
        
        return answer;
    }
}

 

 

📌 기존 코드의 문제점

 

1. 이중배열 생성(arr[][])과 불필요한 메모리 사용 문제

• 문제 조건 제한 사항에서 n은 최대 10^7까지 가능하므로 n x n 크기의 배열을 생성하면 메모리 초과가 발생한다.
• 따라서, 기존 코드의 2차원 방식이 아닌 1차원 배열로 직접 접근하는 방법을 사용해야 한다. 

 

2. 1차원 배열(arr2[]) 변환 문제

• z의 값에 따라 arr[i][j]의 위치를 결정하지 않고, arr[i][j]의 동일한 값을 arr2[]의 모든 인덱스에 덮어쓰고 있기 때문에 정확하지 않는 값이 들어가게 된다. 

 

3. 잘라내기 구현(answer[t] = arr2[t];)문제

• answer 인덱스는 0부터 시작해야하지만, 기존 코드에서는 t에 맞춰서 left값 부터 인덱스가 시작하므로 잘못되었다. 

 

---

 

[ 정답 코드 & 올바른 풀이 ]

📌 정답 코드

class Solution {
    public int[] solution(int n, long left, long right) {
    
        int[] answer = new int[(int)(right - left + 1)];
        
        // 메모리 초과를 막기 위해 2차원 배열이 아닌
        // 처음부터 1차원 배열로 정답 배열 채우기! [1,2,3,2,2,3,3,3,3]
        for(long i =  left; i <= right; i++) { // 2~5
        // 행 열 = 0   1    2
        //  0   i+1, i+2, i+3,    
        //  1   i+2, i+2, i+3,
        //  2   i+3, i+3, i+3
        // [0,0] = 1
        // [0,1], [1,0], [1,1] = 2
        // [0,2], [1,2], [2,0],[2,1],[2,2] = 3
        // [행,열] 형식인데 열과 행 중 큰 수가 채울 숫자가 된다. 
            // [0,2], [0,1], [1,0], [2,1]
            int row = (int)(i / n); //2 / 3 = 0
            int col = (int)(i % n); //2 % 3 = 2
            // answer 인덱스는 0부터 채워져야 함
            answer[(int)(i - left)] = Math.max(row, col)+1;
        } // [3,2,2,3]
        
        return answer;
    }
}