forked from DaleStudy/leetcode-study
-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathwogha95.js
More file actions
127 lines (111 loc) Β· 3.57 KB
/
wogha95.js
File metadata and controls
127 lines (111 loc) Β· 3.57 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
/**
* 3μ°¨ (μκ°, κ³΅κ° λ³΅μ‘λ κ°μ )
* λμΌν downλ°©ν₯, rightλ°©ν₯λ€ μ€μμ λμ΄νλ λ°©λ²
* μ¦, ((m - 1) + (n - 1))! / ((m - 1)! * (n - 1)!)
* (+ ν©ν 리μΌμ μλ λ§€μ° λΉ λ₯΄κ² 컀μ§λ―λ‘ μ€κ° λλμ
μ΄ κ°λ₯ν λλ§λ€ λλμ΄μ integer λ²μλ₯Ό λμ§ μλλ‘ λ°©μ§)
*
* TC: O(M + N)
* 1λΆν° μ΅λ (M - 1) + (N - 1)κΉμ§ μν
*
* SC: O(1)
* κ³μ°μ κ²°κ³Ό λ³μκ° m, nκ³Ό 무κ΄νλ―λ‘ μμμ 곡κ°λ³΅μ‘λ
*/
/**
* @param {number} m
* @param {number} n
* @return {number}
*/
var uniquePaths = function (m, n) {
// 1. downλ°©ν₯, rightλ°©ν₯μ μ
const NUMBER_OF_DOWN = m - 1;
const NUMBER_OF_RIGHT = n - 1;
// 2. factorial κ³μ°μ μν λ³μ
let result = 1;
let factorialOfDown = 1;
let factorialOfRight = 1;
// 3. 'downλ°©ν₯ μ + rightλ°©ν₯ μ'λ§νΌ μννλ©΄μ
for (let number = 1; number <= NUMBER_OF_DOWN + NUMBER_OF_RIGHT; number++) {
result *= number;
// 4. factorial κ°λ€μ΄ 컀μ§μ§ μλλ‘ λλμ μμλλ§λ€ λλ (factorial of down)
if (number <= NUMBER_OF_DOWN) {
factorialOfDown *= number;
if (result % factorialOfDown === 0) {
result /= factorialOfDown;
factorialOfDown = 1;
}
}
// 5. factorial κ°λ€μ΄ 컀μ§μ§ μλλ‘ λλμ μμλλ§λ€ λλ (factorial of right)
if (number <= NUMBER_OF_RIGHT) {
factorialOfRight *= number;
if (result % factorialOfRight === 0) {
result /= factorialOfRight;
factorialOfRight = 1;
}
}
}
return result / factorialOfDown / factorialOfRight;
};
/**
* 2μ°¨ (곡κ°λ³΅μ‘λ κ°μ )
* μ΄μ νμ΄μμ λͺ¨λ νμ κ²½λ‘μλ₯Ό κΈ°μ΅ν νμκ° μλ μ μ νμ©
*
* TC: O(M * N)
* κ²½λ‘ μλ₯Ό κΈ°λ‘νκΈ° μν Nλ°°μ΄ μν * (M - 1)
*
* SC: O(N)
* κ²½λ‘μ κΈ°λ‘μ μν 1μ°¨μ λ°°μ΄
*/
/**
* @param {number} m
* @param {number} n
* @return {number}
*/
var uniquePaths = function (m, n) {
// 1. μ΅μλ¨μ κ²½λ‘μλ λͺ¨λ 1
const numberOfPaths = new Array(n).fill(1);
for (let row = 1; row < m; row++) {
// 2. κ° μ’νμ κ²½λ‘μλ νμ’ν(1μ°¨ νμ΄μ row-1)μ μ’μΈ‘μ’ν(1μ°¨ νμ΄μ column-1)μ ν©
for (let column = 1; column < n; column++) {
numberOfPaths[column] += numberOfPaths[column - 1];
}
}
return numberOfPaths[n - 1];
};
/**
* 1μ°¨
* κ° μ’νμ κ²½λ‘μλ₯Ό κΈ°λ‘νμ¬ dpλ‘ νμ΄
* νμ’νκΉμ§μ κ²½λ‘μ = μλ¨μ’νμμ μ¨ κ²½μ° + μ’μΈ‘μ’νμμ μ¨ κ²½μ°
* dp[row][column] = dp[row - 1][column] + dp[row][column - 1]
*
*
* TC: O(M * N)
* κ²½λ‘μλ₯Ό κΈ°λ‘ν 2μ°¨μ λ°°μ΄μ μ 체 μν
*
* SC: O(M * N)
* κ²½λ‘μ κΈ°λ‘μ μν 2μ°¨μ λ°°μ΄
*/
/**
* @param {number} m
* @param {number} n
* @return {number}
*/
var uniquePaths = function (m, n) {
// 1. κ° μ’λ£κΉμ§μ κ²½λ‘μλ₯Ό κΈ°λ‘νκΈ° μν λ°°μ΄
const numberOfPaths = new Array(m).fill(new Array(n).fill(0));
// 2. μ΅μ’μΈ‘μ μλ μ’νμ κ²½λ‘μλ 1
for (let row = 0; row < m; row++) {
numberOfPaths[row][0] = 1;
}
// 3. μ΅μλ¨μ μλ μ’νμ κ²½λ‘μλ 1
for (let column = 0; column < n; column++) {
numberOfPaths[0][column] = 1;
}
// 4. κ·Έ μΈ κ° μ’νλ λ°λ‘ μ μ’ν(column-1)μ λ°λ‘ μΌμͺ½ μ’ν(row-1)μ κ²½λ‘μμ ν©
for (let row = 1; row < m; row++) {
for (let column = 1; column < n; column++) {
numberOfPaths[row][column] =
numberOfPaths[row - 1][column] + numberOfPaths[row][column - 1];
}
}
return numberOfPaths[m - 1][n - 1];
};