[LeetCode] - 2639. Find the Width of Columns of a Grid

LeetCode는 프로그래밍 문제를 풀며 코딩 실력을 향상할 수 있는 온라인 플랫폼입니다. 다양한 알고리즘 및 데이터 구조 문제를 제공하며, 면접 대비에 유용합니다. 해당 문제는, LeetCode Problems에서 볼 수 있는 난이도 '쉬움 (Easy)' 단계인 "Find the Width of Columns of a Grid" 문제입니다.

--> https://leetcode.com/problems/find-the-width-of-columns-of-a-grid/description/

 

문제 : 

You are given a 0-indexed m x n integer matrix grid. The width of a column is the maximum length of its integers.

For example, if grid = [[-10], [3], [12]], the width of the only column is 3 since -10 is of length 3.

Return an integer array ans of size n where ans[i] is the width of the ith column.

The length of an integer x with len digits is equal to len if x is non-negative, and len + 1 otherwise.

---

Example 1 :

Input : grid = [[1],[22],[333]]

Output : [3]

Explanation : In the 0th column, 333 is of length 3.

 

Example 2 :

Input : grid = [[-15,1,3],[15,7,12],[5,6,-2]]

Output : [3,1,2]

Explanation : In the 0th column, only -15 is of length 3. In the 1st column, all integers are of length 1.

In the 2nd column, both 12 and -2 are of length 2.

 

Constraints :

• m == grid.length
• n == grid[i].length
• 1 <= m, n <= 100
• -10^9 <= grid[r][c] <= 10^9

---

이 문제는 주어진 m x n 크기의 정수 행렬 grid가 있습니다. 열의 너비는 해당 열에 있는 정수의 최대 길이로 정의됩니다.

예를 들어, grid = [[-10], [3], [12]]인 경우, 유일한 열의 너비는 -10의 길이인 3입니다.

정수 배열 ans를 반환하는데, ans[i]는 i번째 열의 너비를 나타냅니다.

정수 x의 길이는 자릿수(len)와 같으며, x가 음수인 경우 len + 1입니다.

 

class Solution {
    public int[] findColumnWidth(int[][] grid) {
        int rows = grid.length;
        int cols = grid[0].length;
        
        int[] res = new int[cols];
        
        for (int c = 0; c < cols; c++) {
            for (int r = 0; r < rows; r++) {
                res[c] = Math.max(res[c], String.valueOf(grid[r][c]).length());
            }
        }
        

        return res;
    }
}

 

주요 변수 및 데이터 구조

• rows 및 cols : 행렬의 행과 열의 개수를 저장합니다.
• res : 각 열의 최대 길이를 저장할 정수 배열입니다.

코드 설명 :

1. 초기화 :
   • rows는 grid의 행의 개수로 초기화됩니다.
   • cols는 grid의 열의 개수로 초기화됩니다.
   • res 배열은 열의 개수 cols만큼의 크기로 초기화됩니다.
2. 열 순회 :
   • c는 각 열을 순회하는 인덱스입니다.
   • 각 열마다, 해당 열의 모든 행(r)을 순회합니다.
3. 최대 길이 계산 :
   • res[c]는 현재 열 c의 최대 길이를 저장합니다.
   • 각 정수를 문자열로 변환하여 그 길이를 계산하고, res[c]와 비교하여 더 큰 값을 res[c]에 저장합니다.
4. 결과 반환 :
   • 모든 열에 대해 최대 길이를 계산한 후, res 배열을 반환합니다.

• 시간 복잡도 : O(m * n)
  • 각 열에 대해 모든 행을 순회하기 때문에, 전체적으로는 행렬의 모든 요소를 한 번씩 방문합니다.
  • 여기서 m은 행의 개수, n은 열의 개수입니다.
  • 문자열 변환 및 길이 계산은 O(1) 시간에 수행됩니다.

• 공간 복잡도 : O(n)
  • 결과를 저장하기 위한 res 배열의 크기는 열의 개수 n에 비례합니다.
  • 추가적으로 사용하는 공간은 고정된 크기의 변수들만 사용하므로, 이는 상수 공간입니다.

---

제 코드가 결과가 별로 좋지 못해서 다른 유저들 솔루션들을 봤는데 이 분꺼가 비교적 접근하기 쉬워 보여서 공유해 봅니다 :

 class Solution {
     public int[] findColumnWidth(int[][] grid) {
        int len = grid.length;
        int len1 = grid[0].length;
        int ans[] = new int[len1];
        for(int i = 0; i < len1; i++)
        {
            long ma = 0;
            for(int j = 0; j < len;j++)
            {
                long c = grid[j][i];
                if(c < 0)
                    c *= -10;
                if(c > ma)
                    ma = c;
            }
            if(ma > 0)
                ans[i] = (int)(Math.log10(ma));
            ans[i]++;
        }
        return ans;
    }
 }
 // Mayank_Nainwal 유저의 코드

 

이 분의 코드를 간략히 설명드리자면 : 

 

• 초기화 :
  • len은 grid의 행의 개수로 초기화됩니다.
  • len1은 grid의 열의 개수로 초기화됩니다.
  • ans 배열은 열의 개수 len1만큼의 크기로 초기화됩니다.
• 열 순회 :
  • i는 각 열을 순회하는 인덱스입니다.
  • 각 열마다, 해당 열의 모든 행(j)을 순회합니다.
• 최대 길이 계산 :
  • ma는 현재 열 i의 최대 자릿수를 저장합니다.
  • 각 정수를 long 타입의 c 변수에 저장합니다.
  • c가 음수이면 -10을 곱하여 부호를 포함한 자릿수를 계산합니다.
  • c가 현재 최대값 ma보다 크면, ma를 c로 갱신합니다.
• 결과 저장 :
  • 최대값 ma가 0보다 크면, ma의 자릿수를 계산하여 ans[i]에 저장합니다.
  • 자릿수를 계산한 후, ans[i]를 1 증가시킵니다 (이는 부호나 0일 경우를 처리하기 위함입니다).
• 결과 반환 :
  • 모든 열에 대해 최대 자릿수를 계산한 후, ans 배열을 반환합니다.

시간, 공간 복잡도는 제 코드랑 동일합니다만 Runtime 결과가 저랑 차이가 조금 있습니다. 

---

내 코드 다른 유저 코드 Runtime 결과