forked from DaleStudy/leetcode-study
-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathEgonD3V.swift
More file actions
113 lines (95 loc) · 3.28 KB
/
EgonD3V.swift
File metadata and controls
113 lines (95 loc) · 3.28 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
import Foundation
class Solution {
func countBits(_ n: Int) -> [Int] {
return solve_2(n)
}
/*
**내장함수를 사용한 풀이**
Runtime: 37 ms (Beats 49.12%)
Time Complexity: O(n * log n)
- 길이가 n인 range를 순회하므로 O(n)
- 정수에 대해 non zero bit를 세는데 O(log n)
> O(n * log n)
Space Complexity: O(n)
- 배열에 값을 저장하며 크기가 n이 되므로 O(n)
Memory: 20.86 MB (Beats 90.106%)
*/
func solve_1(_ n: Int) -> [Int] {
var result: [Int] = []
for num in 0...n {
result.append(num.nonzeroBitCount)
}
return result
}
/*
** Brian Kernighan's Algorithm을 사용한 풀이 **
Runtime: 39 ms (Beats 42.11%)
Time Complexity: O(n * log n)
- 길이가 n인 range를 순회하므로 O(n)
- bitCountWithBrianKernighan 에서 내부 while문 실행마다 num이 절반으로 줄어드므로, 실행횟수는 O(log n)
> O(n * log n)
Space Complexity: O(n)
- 배열에 값을 저장하며 크기가 n이 되므로 O(n)
Memory: 16.01 MB (Beats 67.84%)
*/
func solve_2(_ n: Int) -> [Int] {
func bitCountWithBrianKernighan(_ num: Int) -> Int {
var num = num
var bitCount = 0
while 0 < num {
num &= (num - 1)
bitCount += 1
}
return bitCount
}
var result: [Int] = []
for num in 0...n {
result.append(bitCountWithBrianKernighan(num))
}
return result
}
/*
** MSB에 대해 DP를 사용한 풀이 **
> num의 비트 카운트 = MSB의 비트 카운트(1 고정) + (num - msb)의 비트 카운트
Runtime: 36 ms (Beats 58.48%)
Time Complexity: O(n)
- 0부터 n까지 range를 순회하므로 O(n)
> O(n)
Space Complexity: O(n)
- 길이가 n인 dp 배열을 저장하므로 O(n)
Memory: 21.15 MB (Beats 67.84%)
*/
func solve_3(_ n: Int) -> [Int] {
guard 1 <= n else { return [0] }
var dp = [Int](repeating: 0, count: n + 1)
var msb = 1
for num in 1...n {
if msb << 1 == num {
msb = num
}
dp[num] = 1 + dp[num - msb]
}
return dp
}
/*
** LSB에 대해 DP를 사용한 풀이 **
> num의 비트 카운트 = num을 right shift한 숫자의 비트 카운트 + LSB의 비트 카운트(1 또는 0)
Runtime: 28 ms (Beats 97.08%)
Time Complexity: O(n)
- 0부터 n까지 range를 순회하므로 O(n)
> O(n)
Space Complexity: O(n)
- 길이가 n인 dp 배열을 저장하므로 O(n)
Memory: 21.26 MB (Beats 53.80%)
*/
func solve_4(_ n: Int) -> [Int] {
guard 1 <= n else { return [0] }
var dp = [Int](repeating: 0, count: n + 1)
for num in 1...n {
dp[num] = dp[num >> 1] + (num & 1)
}
return dp
}
}
let solution = Solution()
print(solution.solve_4(0))