-
Notifications
You must be signed in to change notification settings - Fork 0
/
보석 쇼핑.java
93 lines (73 loc) · 2.15 KB
/
보석 쇼핑.java
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
import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Set;
class Solution {
public static int ansLength, ansStart, ansEnd;
public static Set<String> gemSet = new HashSet<>();
public static Map<String, Integer> myGems = new HashMap<>();
public int[] solution(String[] gems) {
for (String gem : gems) {
gemSet.add(gem);
}
ansLength = Integer.MAX_VALUE;
int st = 0;
int en = 0;
myGems.put(gems[0], 1);
while (st <= en && en < gems.length) {
while (st <= en && isDuplicate(gems[st])) {
String targetGem = gems[st];
remove(targetGem);
st++;
}
if (hasAllGems()) {
saveAnswer(en - st + 1, st, en);
String targetGem = gems[st];
remove(targetGem);
st++;
} else {
en++;
if (en == gems.length) {
break;
}
String targetGem = gems[en];
add(targetGem);
}
}
int[] answer = {ansStart + 1, ansEnd + 1};
return answer;
}
public boolean hasAllGems() {
return gemSet.size() == myGems.keySet().size();
}
public void saveAnswer(int length, int st, int en) {
if (length >= ansLength) {
return;
}
// length < ansLength
ansLength = length;
ansStart = st;
ansEnd = en;
}
public void add(String gem) {
if (myGems.containsKey(gem)) {
Integer gemCnt = myGems.get(gem);
myGems.put(gem, gemCnt + 1);
} else {
myGems.put(gem, 1);
}
}
public void remove(String gem) {
if (myGems.containsKey(gem)) {
Integer gemCnt = myGems.get(gem);
if (gemCnt == 1) {
myGems.remove(gem);
} else {
myGems.put(gem, gemCnt - 1);
}
}
}
public boolean isDuplicate(String gem) {
return myGems.containsKey(gem) && myGems.get(gem) >= 2;
}
}