https://leetcode.com/problems/rotate-image/description/
코드설명
구현(Implementation) 을 활용합니다.
In-Place 제약이 없었다면, 매우 간단한 문제입니다. 단순하게 2D Matrix를 새로 만들어서 처리하면 됩니다.
하지만, In-Place 제약조건으로 인해, 2D Matrix를 선언하지않고, 최대한 메모리를 아껴서 그 자리에서 바꾸어야합니다.
위치의 이동지점은 상대위치 관점에서 모두 같다고 생각합니다. 예로 들면, (1,1)에서 (1,2)로 가는것과 (1,2)에서 (2, 2)로 가는 것은 사실상 같습니다. 즉, 회전해서 현재의 위치로 생각하면 됩니다.
저의 경우 In-Place 방식은 아닙니다, Queue를 활용하여 <이동할 위치, 현재Value> 값을 넣어서 처리했습니다.
다른 정답 코드의 경우, 가운데를 기준으로 위아래를 서로 전환해주고, 대각선을 기준으로 전환 과정을 통해서 만듭니다.
이 과정의 경우 메모리 크기가 오직 [N] 개이기에, 효율적입니다. 저의 경우 메모리 크기가 사실상 O(N^2)이기에 문제에서 원하는 답은 아닙니다.
코드
정답코드1입니다. Space Complexity = O(N^2)
class Solution {
public void rotate(int[][] matrix) {
int n = matrix.length;
Queue<int[]> q = new LinkedList<>();
for(int r=0; r<n; r++){
for(int c=0; c<n; c++){
q.offer(new int[]{c, n - 1 - r, matrix[r][c]});
}
}
while(!q.isEmpty()){
int[] temp = q.poll();
int r = temp[0];
int c = temp[1];
int v = temp[2];
matrix[r][c] = v;
}
}
}
오답코드1입니다.
처음에 직접 모두 옮기는 과정입니다. 하지만, 이 경우에 2D MAtrix는 아니지만, nextLine 1차원 배열이 사용됩니다.
class Solution {
public void rotate(int[][] matrix) {
}
void rotate(int[][] matrix, int sr, int sc){
int[] nextLine = new int[size];
for(int r = 0; r < size; r++){
nextLine[r] = adj[sr + r][sc];
}
for(int r = 0; r < size; r++){
adj[sr + r][sc] = nextLine[r];
}
int[] nextnextLine = new int[size];
for(int c = size - 1; c >= 0; c--){
nextnextLine[size - 1 - c] = adj[sr + size - 1][c];
}
for(int c = size - 1; c >= 0; c--){
adj[sr + r ][sc + c] = nextLine[c];
}
}
}