[Matrix][Medium] 54. Spiral Matrix

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

 

Q. m x n matrix가 주어질 때, 모든 matrix의 값을 나선 형태로 반환하라. 

 

 

Solution. 

 나선으로 하나씩 돌게 로직을 만들다 보니, 예외 상황이 많이 생긴다. 

 따라서 메모리를 조금 더 쓰고, 간결한 접근법을 찾는다. 

 외피부터 시계방향으로 데이터를 얻는다. 

 map, dictionary를 사용해, 중복을 방지 한다. 

 다음 한단계 내피(x+1, y+1)로 들어온다. 

 이 과정을 Width/2 까지 진행한다. 

 

 많은 중복이 생기겠지만, 로직을 단순화 하고, 

 set 자료구조를 써서 중복데이터를 억제한다. 

 

 

int CellToIndex(int iX, int iY, int W)
{
    return W*iY + iX;
}
bool IsValid(int[][] matrix, int iX, int iY)
{
    if(iX<0 || iY<0)    return false;
    if(iY>=matrix.Length || iX>=matrix[0].Length)   return false;
    return true;
}
void GetValueLToR(int[][] matrix, int iX, int iY, int count, IList<int> listOut, Dictionary<int, int> dictFreq)
{
    for(int x = 0; x < count; ++x)
    {
        if(IsValid(matrix, iX+x, iY) && !dictFreq.ContainsKey(CellToIndex(iX+x, iY, matrix[0].Length)))
        {
            dictFreq.Add(CellToIndex(iX+x, iY, matrix[0].Length), 1);
            listOut.Add(matrix[iY][iX+x]);
        }
    }
}
void GetValueTToD(int[][] matrix, int iX, int iY, int count, IList<int> listOut, Dictionary<int, int> dictFreq)
{
    for(int y = 0; y < count; ++y)
    {
        if(IsValid(matrix, iX, iY+y) && !dictFreq.ContainsKey(CellToIndex(iX, iY+y, matrix[0].Length)))
        {
            dictFreq.Add(CellToIndex(iX, iY+y, matrix[0].Length), 1);
            listOut.Add(matrix[iY+y][iX]);
        }
    }
}
void GetValueRToL(int[][] matrix, int iX, int iY, int count, IList<int> listOut, Dictionary<int, int> dictFreq)
{
    for(int x = 0; x < count; ++x)
    {
        if(IsValid(matrix, iX-x, iY) && !dictFreq.ContainsKey(CellToIndex(iX-x, iY, matrix[0].Length)))
        {
            dictFreq.Add(CellToIndex(iX-x, iY, matrix[0].Length), 1);
            listOut.Add(matrix[iY][iX-x]);
        }

    }
}
void GetValueDToT(int[][] matrix, int iX, int iY, int count, IList<int> listOut, Dictionary<int, int> dictFreq)
{
    for(int y = 0; y < count; ++y) 
    {
        if(IsValid(matrix, iX, iY-y) && !dictFreq.ContainsKey(CellToIndex(iX, iY-y, matrix[0].Length)))
        {
            dictFreq.Add(CellToIndex(iX, iY-y, matrix[0].Length), 1);
            listOut.Add(matrix[iY-y][iX]);
        }
    }
}

public IList<int> SpiralOrder(int[][] matrix) 
{
    IList<int> listOut = new List<int>();

    int H = matrix.Length;
    int W = matrix[0].Length;
    Dictionary<int, int> dictFreq = new Dictionary<int, int>();
    for(int k = 0; k <= W/2; ++k)
    {
        GetValueLToR(matrix, k, k, W-2*k, listOut, dictFreq);  
        GetValueTToD(matrix, W-k-1, k, H-2*k, listOut, dictFreq);  
        GetValueRToL(matrix, W-k-1, H-k-1, W-2*k, listOut, dictFreq);  
        GetValueDToT(matrix, k, H-k-1, H-2*k, listOut, dictFreq);  
    }
    return listOut;
}

 

 

적절한 결과를 얻었다. 

 

 

Note) 이 문제도 참 간단치 않다. 

 관련 연계 문제도 계속 풀어보자.