[Leetcode] 48. Rotate Image

Identifying the Problem

주어진 matrix를 90도 회전한다.

단, 새로운 matrix를 생성하면 안 된다.

Organizing thoughts

슬라이딩 퍼즐

어렷을 때 슬라이딩 퍼즐 가지고 논게 문제푸는 데 도움이 된 것 같다.

1	2	3
4	5	6
7	8	9

이런 경우

1
4	5	6
7	8	9

옆에 두칸을 [2,3]으로 따로 빼두고,
1을 3번자리로 옮기고,

4를 2번자리로 옮기고

7을 1번 자리로 옮기고

8을 4번 자리로 옮기고

...

6을 8번 자리로 옮긴다.

이후, 6번과 9번 자리에 2,3을 집어 넣는다.

 

이를 양파 까듯 n x n 테두리, (n-2) x (n-2) ... 1 x 1 까지 반복한다.

 

Sourcecode

void rotate(int** matrix, int matrixSize, int* matrixColSize)
{
    int n = matrixSize;
    int* store = malloc(sizeof(int) * (n-1)); //위 끝을 저장할 배열
    
    for(int i=0; i<(n+1)/2; i++)
    {
        for(int k = i+1; k<= n-i-1; k++)
            store[k-i-1] = matrix[i][k]; // 위 끝값 저장
        
       
        for(int k = 0 ; k< n-2*i; k++)
            matrix[i][n-1-k-i] = matrix[k+i][i]; // 위 끝을 왼 끝으로 채우기
        
       

        for(int k = 0 ; k< n-2*i; k++)
            matrix[k+i][i] = matrix[n-1-i][k+i]; //왼 끝을 아래 끝으로 채우기
        
     
        
        for(int k = 0 ; k< n-2*i; k++)
            matrix[n-1-i][k+i] = matrix[n-1-k-i][n-1-i]; //아래 끝을 우끝으로 채우기

        
        for(int k = 0 ; k< n-2*i -1; k++)   
            matrix[k+1+i][n-1-i] = store[k]; //우끝을 저장한 위 끝으로 채우기
        
        
    }
}

 

Mistake

• 진행 횟수와 좌표의 위치는 다르기에 자세히 생각하기
  n x n -> (n-2) x (n-2) 과정에서 시작 점의 좌표를 0,0 그대로 했음