[LeetCode- Ch3. 배열] 7. 나선형 매트릭스 #

https://leetcode.com/problems/spiral-matrix/

Spiral Matrix - LeetCode

 

 

---

나선형 매트릭스

:m x n의 요소로 이루어진 매트릭스로, 나선형 순으로 모든 요소를 출력 [동글뱅이]

-> 상하좌우 위치 좌표값 변경을 이용해 문제해결

[0,0]:1, [0,1]:2, [0,2]:3, [0,3]:4
[1,0]:5, [1,1]:6, [1,2]:7, [1,3]:8
[2,0]:9, [2,1]:10, [2,2]:11, [2,3]:12

문제 해결 -> 방향을 기준으로 분류, 오른쪽방향, 아래쪽방향, 왼쪽방향, 위쪽방향, 오른쪽방향

#규칙찾기

1. {00, 01, 02, 03} : 오른쪽으로 이동시
   •  int rowStart =0, int rowEnd=2, matrix.length-1;
   •  int colStart =0, int colEnd=3, matrix[0].length-1;
   • 즉, rowStart=0은 그대로 int colStart=0, intcolEnd=3, 끝나고 rowStart++ colStart가 0에서 colEnd인 3까지 :
     for(int i=colStart; i<=colEnd; i++)
   • 결과값행렬에 rowStart은 0 고정, i값 증가할때마다 추가 :
     {result.add(matrix[rowStart][i]);} result는 ArrayList로 List를 담는다.
   • 한행 고정하고, 칼럼이 증가하면서 한행이 끝났기 때문에 : rowStart++;
2. {03, 13, 23} : 아래쪽으로 이동시
   • int rowStart =0, int rowEnd=2, matrix.length-1;
   • int colStart =0, int colEnd=3, matrix[0].length-1;
   • colEnd=3은 그대로 int rowStart=1, int rowStart=2로 증가, 끝나고 colEnd-- rowStart가 0에서 rowEnd인 2까지 : 
     for(int i=rowStart; i<=rowEnd; i++)
   • 결과값행렬에 칼럼인 colEnd는 0 고정,  행은 i값 증가할때마다 추가 :
     {result.add(matrix[i][colEnd]); result는 ArrayList로 List를 담는다.
   • 한 칼럼을 고정하고, 행이 증가하면서 한 칼럼이 끝났기 때문에 : colend--;
3. {23, 22, 21, 20} : 왼쪽으로 이동시
   • rowEnd=2은 그대로 int colEnd=에서 int colStart=0까지 감소, 끝나고 rowEnd--
     while문 안에서 rowStart가 내부적으로 증가:
     [rowStart++;] : if(rowStart<=rowEnd{ colEnd가 3에서 colStart인 0까지 :
      for(int i=colEnd; i>=colStart; i--)
   • 결과값행렬에 행인 rowEnd는 2 고정,  칼럼은 i값 감소할때마다 추가 :
     {result.add(matrix[rowEnd][i]);}} result는 ArrayList로 List를 담는다.
   • 한 행을 고정하고, 칼럼이 감소하면서 한 행이 끝났기 때문에 : rowEnd--;
4. {20, 10} :위쪽으로 이동시
   • colStart=0 그대로 int rowEnd=1, int rowEnd=0으로 감소, 끝나고 colStart++
     while문 안에서 colStart가 내부적으로 증가 [colStart++;] : 
     if(colStart<=colEnd){ rowEnd가 2에서 rowStart인 1까지 :
      for(int i=rowEnd; i>=rowStart; i--)
   • 결과값행렬에 칼럼인 colStart는 0 고정, 행은 i값 감소할때마다 추가:
     {result.add(matrix[i][colStart]);}} result는 ArrayList로 List를 담는다.
   • 한 칼럼을 고정하고, 행이 감소하면서 한 칼럼이 끝났기 때문에 : colStart++;

#갔던 곳 다시 안가도록 조건 처리

       

    if(rowStart<=rowEnd){//위쪽 방향}

    if(colStart<=colEnd){//오른쪽 방향}

 

---

class Solution {
    public List<Integer> spiralOrder(int[][] matrix) {
        List<Integer> result = new ArrayList<>();
        if(matrix==null||matrix.length==0) {
			return result;
		}
        
        int rowStart=0;
        int rowEnd=matrix.length-1;
        
        int colStart=0;
        int colEnd=matrix[0].length-1;
        
        while(rowStart<=rowEnd && colStart<=colEnd){
            for(int i=colStart; i<=colEnd; i++){
                result.add(matrix[rowStart][i]);
            }
            rowStart++;
            for(int i=rowStart; i<=rowEnd;i++){
                result.add(matrix[i][colEnd]);
            }
            colEnd--;
            
            //이미 간 곳은 가지 않아야 하므로, 범위체크를 수행한다.
            if(rowStart<=rowEnd){
            for(int i=colEnd; i>=colStart; i--){
                result.add(matrix[rowEnd][i]);
            }
            }
            rowEnd--;
            if(colStart<=colEnd){
            for(int i=rowEnd; i>=rowStart;i--){
                result.add(matrix[i][colStart]);
            }
            }
            colStart++;
        }
        
        return result;
        
    }
}

 

 

---

반복문 탈출조건과 조건문

1. rowStart<=rowEnd && colStart<=colEnd;

2. 위쪽 방향 : rowStart<=rowEnd;

3. 왼쪽 방향 : colStart<=colEnd;

 

class Solution {
    public List<Integer> spiralOrder(int[][] matrix) {
        int m=matrix.length;
        int n=matrix[0].length;
        
        int rowStart=0;
        int rowEnd=m-1;
        int colStart=0;
        int colEnd=n-1;
        List<Integer> answer= new ArrayList<>();
        while(rowStart<=rowEnd && colStart<=colEnd){
            //1.
            for(int i=colStart; i<=colEnd;i++){
                answer.add(matrix[rowStart][i]);
            }
            rowStart++;

            //2.
            for(int i=rowStart; i<=rowEnd;i++){
                answer.add(matrix[i][colEnd]);
            }
            colEnd--;
            if(rowStart<=rowEnd){
            //3.
            for(int i=colEnd; i>=colStart; i--){
                answer.add(matrix[rowEnd][i]);
            }
            }
            rowEnd--;

            if(colStart<=colEnd){
            //4.
            for(int i=rowEnd; i>=rowStart;i--){
                answer.add(matrix[i][colStart]);
            }
            colStart++;
            }
        }
        return answer;
    }
}