[LeetCode/Easy] 1030. Matrix Cells in Distance Order

1. Input

1) int rows

2) int cols

3) int rCenter

4) int cCenter

 

2. Output

1) rows*cols 행렬의 (rCenter, cCenter)에서부터 가까운 순서로 좌표를 담은 배열을 반환

- (rCenter, cCenter)에서부터 같은 거리에 있는 여러 개의 점을 담을 때는 어떤 순서든 상관없다..

- 두 점 (r1, c1), (r2, c2) 사이의 거리를 구할 때는 |r1 - r2| + |c1 - c2|를 계산하여 구한다.

 

3. Constraint

1) 1 <= rows, cols <= 100

2) 0 <= rCenter < rows

3) 0 <= cCenter < cols

 

4. Example

Input: rows = 2, cols = 2, rCenter = 0, cCenter = 1 -> Output: [[0,1],[0,0],[1,1],[1,0]]

Input: rows = 2, cols = 3, rCenter = 1, cCenter = 2 -> Output: [[1,2],[0,2],[1,1],[0,1],[1,0],[0,0]]

 

5. Code

1) 첫 코드(2023/06/07)

class Solution {
    public int[][] allCellsDistOrder(int rows, int cols, int rCenter, int cCenter) {
        int[][] ans = new int[rows*cols][2];
        for(int i=0 ; i<ans.length ; i++){
            ans[i][0] = i/cols;
            ans[i][1] = i%cols;
        }
        int[] temp = {0,0};
        for(int i=0 ; i<ans.length-1 ; i++) {
            int j = i;
            while(j>=0 && d(ans[j], rCenter, cCenter) > d(ans[j+1], rCenter, cCenter)){
                temp = ans[j];
                ans[j] = ans[j+1];
                ans[j+1] = temp; j--;
            }
        }
        return ans;
    }

    static int d(int[] arr, int x, int y){
        return Math.abs(arr[0]-x) + Math.abs(arr[1]-y);
    }
}

- 5%, 20%

- 삽입 정렬 말고 다른 걸로 바꾸면 더 좋겠는데..

 

2) 퀵정렬로 바꿔본 코드(2023/06/07)

class Solution {
    static int x;
    static int y;
    public int[][] allCellsDistOrder(int rows, int cols, int rCenter, int cCenter) {
        int[][] ans = new int[rows*cols][2];
        x = rCenter; y = cCenter;
        for(int i=0 ; i<ans.length ; i++){
            ans[i][0] = i/cols;
            ans[i][1] = i%cols;
        }
        quicksort(ans, 0, ans.length-1);
        return ans;
    }

    static void quicksort(int[][] arr, int start, int end) {
        if(start>=end)
            return;
        
        int pivot = d(arr[start]);
        int i = start+1, j = end;
        int[] temp = {0,0};
    
        while(i<=j) {
            while(i<=end && d(arr[i])<=pivot) 
                i++;
            while(j>start && d(arr[j])>=pivot)
                j--;
            if(i>j) {
                temp = arr[j];
                arr[j] = arr[start];
                arr[start] = temp;
            } else {
                temp = arr[j];
                arr[j] = arr[i];
                arr[i] = temp;
            }
        }
        quicksort(arr, start, j-1);
        quicksort(arr, j+1, end);
    }

    static int d(int[] arr){
        return Math.abs(arr[0]-x) + Math.abs(arr[1]-y);
    }
}

- 33%, 26%

- 내가 좀 더 똑똑해질 때까지 기다려야겠다..ㅎ