Lv.2 : n^2 배열 자르기

👉 문제링크

프로그래머스

---

---

🔸 문제 분석 🔸

• n x n 격자판에 (0, 0) 부터 (n - 1, n - 1)까지 파동이 퍼지듯 숫자를 채운다.
• 각 행을 순서대로 이어 붙인 뒤, 0부터 n-1 중 left ~ right를 잘라서 int 배열로 반환한다.

🔸 문제 풀이 🔸

• 격자판의 숫자는 1 ~ n 으로 채우지만, 인덱스는 0 ~ n-1 이라는 점에 주의한다.
• n의 범위가 100만이고, left, right는 n^2까지 주어진다고 한다.
  • 하지만 반환 배열이 int 형이고 문제 조건에 rifht - left는 1만 미만이라고 주어졌다.
  • 격자판에 값을 전부 저장하면 100만 * 100만 크기의 배열이므로 메모리를 초과한다.
  • 따라서 저장하지 않고, 인덱스만 이동하며 정답 배열을 만들어내 반환한다.
• 풀이를 위해 3회 코드를 작성했다
  • 첫 풀이는 격자판 값을 저장하려고 해서 메모리 초과가 났다.
  • 두 번째 풀이는 left와 right가 격자판에서 같은 행인지 확인해서 따로 처리한 코드로 정답이 나오긴 했다.
  • 세 번째 풀이는 다른 사람들의 풀이를 보고 리펙토링 한 것인데, left와 right를 구분해 따로 처리 할 필요가 없었다.

---

🔸 코드 1 : 오답 코드 🔸

class Solution {
    public int[] solution(int n, long left, long right) {
        
        int[][] arr = new int[n][n];
        
        for(int i = 0; i < n; i++) {
            for(int j = 0; j <= i; j++) {
                arr[i][j] = i+1;
                arr[j][i] = i+1;
            }
        }
        
        int[] answer = new int[(int)(right-left)+1];
        int cnt = 0;
        
        for(int i = (int)left; i <= (int)right; i++) {
            answer[cnt++] = arr[i/n][i%n];
        }
        
        return answer;
    }
}

🔸 코드 해석 🔸

• 격자판의 값을 저장하고, 인덱스를 이동하며 answer 배열을 만드는 방식이다.
• 메모리 초과가 난다.

---

🔸 코드 2 : 정답 이지만 비효율적 🔸

class Solution {
    public int[] solution(int n, long left, long right) {
        int[] answer = new int[(int)(right-left)+1];
        
        int lr = (int)(left / n);   // left row
        int lc = (int)(left % n);   // left col
        int rr = (int)(right / n);  // right row
        int rc = (int)(right % n);  // right col
                
        int cnt = 0;
        
        if(lr == rr) {
            for(int i = lc; i <= rc; i++) {
                answer[cnt++] = (lr > i ? lr : i) + 1;
            }
        } else { // lr < rr
            // row == lr
            for(int col = lc; col < n; col++) {
                answer[cnt++] = (lr > col ? lr : col) + 1;
            }
            
            // lr < row < rr
            for(int row = lr + 1; row < rr; row++) {
                for(int col = 0; col < n; col++) {
                    answer[cnt++] = (row > col ? row : col) + 1;
                }
            }
            
            // row == rr
            for(int col = 0; col <= rc; col++) {
                answer[cnt++] = (rr > col ? rr : col) + 1;
            }
        }  
        
        return answer;
    }
}

🔸 코드 해석 🔸

• left와 right의 행과 열 인덱스를 lr, lc, rr, rc로 나눠 사용했다.
  • 같은 행이라면 열만 이동해서 값을 저장한다.
  • 다른 행이라면 left의 행, right의 행, 둘 사이의 행으로 나눠 값을 저장한다.

---

🔸 코드 2 : 최종 코드 🔸

class Solution {
    public int[] solution(int n, long left, long right) {
        
        int[] answer = new int[(int)(right-left)+1];
        int cnt = 0;
        
        for(long i = left; i <= right; i++) {
            answer[cnt++] = (i/n > i%n ? (int)(i/n) : (int)(i%n)) + 1;
        }
        
        return answer;
    }
}

🔸 코드 해석 🔸

• 격자판의 값은 행과 열 인덱스 중 큰 값이라는 원리가 핵심이다.
• 또한 값은 1부터 n이기 때문에 인덱스에 +1 로 계산해주어야 한다.

---

🔸 end 🔸

• 2차원 배열에서 칸의 순서의 몫과 나머지로 행열 인덱스를 구할 수 있다는 원리를 사용한 문제이다.
• 다른 사람의 풀이는 참고만 했는데, 이번엔 직접 리팩토링해보니 훨씬 도움이 된 것 같다.
  • 앞으로도 시간이 너무 오래 걸리지 않았다면 리팩토링을 많이 해보면 좋을 것 같다.
• 눈에 띄는 풀이 중에는 java의 Stream을 이용한 한 줄 풀이가 있었는데 처음엔 이해가 안가다가 리팩토링 후에는 이해 할 수 있었다.
  • Stream 문법은 잘은 몰라서 나중에 한 번 공부해 볼 생각이다.
• 채점 결과는 왼쪽이 코드 2, 오른쪽이 코드 3이다.
  • 코드 3이 조금 더 느린대신 메모리는 적게 쓰는 것 같은데, 몫과 나머지 계산이 중복으로 일어나서 조금 더 느린 것 같다. 메모리는 코드 2가 for문 속에서 선언을 몇 번 하기 때문에 더 소모 되는 것으로 보인다.