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
66 lines (60 loc) ยท 2.22 KB
/
jdalma.kt
File metadata and controls
66 lines (60 loc) ยท 2.22 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
package leetcode_study
import io.kotest.matchers.collections.shouldContainExactlyInAnyOrder
import org.junit.jupiter.api.Test
class `3sum` {
fun threeSum(nums: IntArray): List<List<Int>> {
return usingTwoPointer(nums)
}
/**
* 1. ์ ์ ๋ฐฐ์ด์ ์ํํ๋ฉฐ ๋ชจ๋ ํ์ธํ๋ค. (์๊ฐ์ด๊ณผ)
* TC: O(n^3), SC: O(n)
*/
private fun usingIterative(nums: IntArray): List<List<Int>> {
val result = mutableSetOf<List<Int>>()
for (first in nums.indices) {
for (second in first + 1 until nums.size) {
for (third in second + 1 until nums.size) {
if (nums[first] + nums[second] + nums[third] == 0) {
result.add(listOf(nums[first], nums[second], nums[third]).sorted())
}
}
}
}
return result.toList()
}
/**
* 2. ์
๋ ฅ๋ฐ์ ์ ์ ๋ฐฐ์ด์ ์ ๋ ฌํ์ฌ ์ํํ๋ฉด์ ์์๋ฅผ ํฉ์ฐํ์ฌ 0๊ณผ ๋น๊ตํ ๊ฒฐ๊ณผ๋ฅผ ๊ธฐ์ค์ผ๋ก ํฌ ํฌ์ธํฐ์ ๊ฐ์ ์กฐ์ํ๋ค.
* TC: O(n^2), SC: O(n)
*/
private fun usingTwoPointer(nums: IntArray): List<List<Int>> {
val sortedNumbers = nums.sorted()
val result = mutableSetOf<List<Int>>()
for (index in nums.indices) {
var left = index + 1
var right = nums.size - 1
while (left < right) {
val sum = sortedNumbers[index] + sortedNumbers[left] + sortedNumbers[right]
if (sum == 0) {
result.add(listOf(sortedNumbers[index], sortedNumbers[left], sortedNumbers[right]))
left++
right--
} else if (sum < 0) {
left++
} else {
right--
}
}
}
return result.toList()
}
@Test
fun `์
๋ ฅ๋ฐ์ ์ ์ ๋ฐฐ์ด์ ์ธ ๊ฐ์ ์์์ ํฉ์ด 0์ด ๋๋ ๋ฆฌ์คํธ๋ฅผ ๋ฐํํ๋ค`() {
threeSum(intArrayOf(-1,0,1,2,-1,-4)) shouldContainExactlyInAnyOrder listOf(
listOf(-1,-1,2),
listOf(-1,0,1)
)
threeSum(intArrayOf(0,0,0)) shouldContainExactlyInAnyOrder listOf(
listOf(0,0,0)
)
}
}