forked from DaleStudy/leetcode-study
-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathjdalma.kt
More file actions
58 lines (48 loc) Β· 1.54 KB
/
jdalma.kt
File metadata and controls
58 lines (48 loc) Β· 1.54 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
package leetcode_study
import io.kotest.matchers.shouldBe
import org.junit.jupiter.api.Test
/**
* 0,0 μμ μλ λλ μ€λ₯Έμͺ½μΌλ‘λ§ μ΄λ κ°λ₯νλ€.
*/
class `unique-paths` {
fun uniquePaths(row: Int, col: Int): Int {
return if (row <= 1 || col <= 1) 1
else usingArray(row, col)
}
/**
* TC: O(n * m), SC: O(n * m)
*/
private fun usingGrid(row: Int, col: Int): Int {
val grid = Array(row) { IntArray(col) }
(0 until row).forEach { grid[it][0] = 1 }
(0 until col).forEach { grid[0][it] = 1 }
for (i in 1 until row) {
for (j in 1 until col) {
grid[i][j] = grid[i - 1][j] + grid[i][j - 1]
}
}
return grid[row - 1][col - 1]
}
/**
* μ΄μ λΌμΈμ λ°°μ΄λ§ κΈ°μ΅νμ¬λ λλ―λ‘ κ³΅κ° λ³΅μ‘λλ₯Ό μλμ κ°μ΄ μ€μΌ μ μλ€.
* TC: O(n * m), SC: O(m)
*/
private fun usingArray(row: Int, col: Int): Int {
var dp = IntArray(col)
for (i in 0 until row) {
val tmp = IntArray(col)
for (j in 0 until col) {
if (i == 0 && j == 0) tmp[j] = 1
else if (j > 0) tmp[j] = dp[j] + tmp[j - 1]
else tmp[j] = dp[j]
}
dp = tmp
}
return dp.last()
}
@Test
fun `μΌμͺ½ μλ¨ λͺ¨μ리μμ μ€λ₯Έμͺ½ μλ¨ λͺ¨μλ¦¬λ‘ λλ¬ν μ μλ κ³ μ κ²½λ‘μ μλ₯Ό λ°ννλ€`() {
uniquePaths(3, 7) shouldBe 28
uniquePaths(3, 2) shouldBe 3
}
}