99클럽 코테 스터디 40일차 TIL - [LeetCode] Unique Paths (Java)

📌 오늘의 학습 키워드

[LeetCode] Unique Paths Java)
https://leetcode.com/problems/unique-paths/description/

📌 공부한 내용 본인의 언어로 정리하기

문제 탐색하기

입력 : 첫번째 줄-부등호 문자의 개수 k
두번째 줄-k개의 부등호 기호 (공백으로 구분)
출력 : 첫번째 줄-부등호 관계를 만족하는 k+1 자리의 최대, 최소 정수
두번째 줄-부등호 관계를 만족하는 k+1 자리의 최소 정수

가능한 시간복잡도

O(n!)

알고리즘 선택

dp

📌 코드 설계하기

1. 먼저 k를 입력받고, k개의 부등호를 배열 operators에 저장한다.
2. dfs 함수는 현재까지의 숫자 조합 num과 깊이 depth를 매개변수로 받아 백트래킹을 진행한다.
3. 숫자 i를 선택하여 조건에 맞으면 다음 단계로 이동하고, k 길이에 도달하면 해당 숫자 조합을 results 리스트에 추가한다.
4. check 함수는 부등호 조건을 확인하는 함수로, 현재 숫자와 다음에 선택할 숫자가 주어진 부등호를 만족하는지 확인한다.
5. 모든 가능한 조합을 results 리스트에 추가한 후, 이를 정렬하여 최대값과 최소값을 출력한다.

📌 오늘의 회고

어떤 문제가 있었고, 나는 어떤 시도를 했는지

어떻게 해결했는지

무엇을 새롭게 알았는지

내일 학습할 것은 무엇인지

구현

📌 정답 코드

class Solution {
    public int uniquePaths(int m, int n) {
        // dp 배열 생성
        int[][] dp = new int[m][n];

        // 첫 번째 열의 모든 위치에 1을 설정 (오직 아래로 이동 가능)
        for (int i = 0; i < m; i++) {
            dp[i][0] = 1;
        }

        // 첫 번째 행의 모든 위치에 1을 설정 (오직 오른쪽으로 이동 가능)
        for (int j = 0; j < n; j++) {
            dp[0][j] = 1;
        }

        // dp 배열을 채움
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                // 위에서 오는 경로 수 + 왼쪽에서 오는 경로 수
                dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
            }
        }

        // 오른쪽 하단의 경로 수 반환
        return dp[m - 1][n - 1];
    }
}