1 분 소요

문제

문제 링크

class Solution:

    def uniquePaths(self, m: int, n: int) -> int:

        array = [[0] * n for _ in range(m)]

        for i in range(m):

            array[i][0] = 1

        for j in range(n):

            array[0][j] = 1

  

        for i in range(1, m):

            for j in range(1, n):

                array[i][j] = array[i - 1][j] + array[i][j - 1]

        return array[m-1][n-1]

Main Idea

  • 2차원 배열을 만들어서 좌표 정리
  • 각 경우의 수를 더해서 최종 값 출력

예를 들어서 가로가 3 세로가 5인경우

1  1  1
1  2  3
1  3  6
1  4 10
1  5 15

Time Complexity & Space Complexity

시간 복잡도:

  1. 배열 초기화: 2차원 배열을 초기화하는데 O(m * n)의 시간이 걸린다.
  2. 첫 번째 열과 첫 번째 행 초기화: 각각 O(m)과 O(n)의 시간이 걸린다.
  3. 2차원 배열을 사용하므로 O(n^2)

따라서 전체 시간 복잡도는 O(n^2)

공간 복잡도:

  • 2차원 배열 array을 사용하여 m x n 크기의 격자를 저장한다. 따라서 공간 복잡도는 O(m * n)다.

코드의 시간 복잡도는 공간 복잡도와 같은 O(m * n)이며, 입력 크기인 m과 n에 선형적으로 비례하는 복잡도를 가지고 있다.

댓글남기기

참고