-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathMaxCounters.java
More file actions
74 lines (61 loc) · 1.88 KB
/
MaxCounters.java
File metadata and controls
74 lines (61 loc) · 1.88 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
package codility;
import java.util.Arrays;
public class MaxCounters {
// O(N*M)
// public static int[] solution(int N, int[] A) {
// // write your code in Java SE 8
// int[] counters = new int[N];
//
// for (int i : A) {
// if (i == N + 1) {
// int max = findMaximumValue(counters);
// Arrays.fill(counters, max);
// } else {
// counters[i - 1]++;
// }
// }
//
// return counters;
// }
// 최대화 쥐어 짜내기!!
// O(N + M)
public static int[] solution(int N, int[] A) {
int[] counters = new int[N];
int max = 0; // max 값을 기록
int correctionMax = 0; // maxCounter를 만났을 때 보정해줄 correctionMax
for (int i : A) {
if (i == N + 1) {
correctionMax = max;
} else {
// correctionMax 값보다 작다면 correctionMax + 1
counters[i - 1] = counters[i - 1] < correctionMax ? correctionMax + 1 : counters[i - 1] + 1;
// max 기록
if (counters[i - 1] > max) {
max = counters[i - 1];
}
}
}
for (int i = 0; i < counters.length; i++) {
if (counters[i] < correctionMax) {
counters[i] = correctionMax;
}
}
return counters;
}
public static int findMaximumValue(int[] array) {
int max = Integer.MIN_VALUE;
if (array.length == 0)
return -1;
for (int i = 0; i < array.length; i++) {
if (max < array[i]) {
max = array[i];
}
}
return max;
}
public static void main(String[] args) {
int test_N = 5;
int[] test_A = new int[]{3, 4, 4, 6, 1, 4, 4};
solution(test_N, test_A);
}
}