문제
1차 풀이 (2020.11.16)
시작
for문 2개 돌리면서 O(N^2)로 돌리면 정말 쉽겠지만, 그러라고 낸 문제는 아니라 다른 방법을 고민해보았다.
우선 gems[] 탐색을 하면서 하나씩 다른 객체에 저장해가면서, 모든 종류의 gem이 포함되었는지 체크하면 되겠다고 생각했다.
여기까지는 생각했는데, 이 값들을 저장할 자료구조가 잘 떠오르지 않아서 구글링을 통해 다른 사람의 풀이를 참고했다.
그렇게 사용하기로 한 자료구조와 변수는 다음과 같다.
gemType: 순서가 중요하지 않고 빠른 검색이 요구되었기 때문에HashSet사용gemsToBuy: a부터 b까지의 gems를 순서대로 저장해야 했기 때문에Queue사용gemsToBuyCount:Queue에 저장된 각 gems들의 count를 저장해야 했기 때문에HashMap사용
메소드
shopGems()
gems[]를 순서대로 탐색하면서 gem을 gemsToBuy에 담고, 조건을 체크하여 답을 업데이트 한다.
removeDuplicateStartGem()
gemsToBuy의 맨 첫 번째 gem이 맨 뒤에 또 들어 온다면 최단 구간이 아니게 되므로, 맨 첫 번째 gem을 삭제하는 메소드다. 이 때 gemsToBuyCount를 통해 이미 존재하는 gem인지 아닌지 확인할 수 있다.
updateAnswer()
gemsToBuy에 모든 gemType이 포함되어 있고, gemsToBuy의 길이가 현재까지 구한 최단 구간의 길이보다 작은 경우 최종 답을 업데이트한다.
실수
updateAnswer에서 size 체크하는 조건을 빼먹었다.
새로 배운 것
자료구조를 떠올리는 게 쉽지 않았다. 배열로 처리해야 빠르다는 강박이 있었는데, 그럴 필요 없이 다양한 자료구조를 적재적소에 활용하는 것이 효율성을 높이는 데에 중요하다는 것을 깨달았다.
코드
import java.util.*;
public class Solution {
private static Set<String> gemType = new HashSet<>();
private static Queue<String> gemsToBuy = new LinkedList<>();
private static Map<String, Integer> gemsToBuyCount = new HashMap<>();
private static int startIndex;
private static int answerStartIndex;
private static int answerSize = Integer.MAX_VALUE;
public int[] solution(String[] gems) {
countGemType(gems);
shopGems(gems);
return new int[]{answerStartIndex + 1, answerStartIndex + answerSize};
}
private void countGemType(String[] gems) {
gemType.addAll(Arrays.asList(gems));
}
private void shopGems(String[] gems) {
for (String gem : gems) {
addGemsToBuy(gem);
removeDuplicateStartGem();
updateAnswer();
}
}
private void addGemsToBuy(String gem) {
gemsToBuy.add(gem);
updateGemsToBuyCount(gem);
}
private void updateGemsToBuyCount(String gem) {
if (gemsToBuyCount.containsKey(gem))
gemsToBuyCount.put(gem, gemsToBuyCount.get(gem) + 1);
else
gemsToBuyCount.put(gem, 1);
}
private void removeDuplicateStartGem() {
while (true) {
String startGem = gemsToBuy.peek();
int startGemCount = gemsToBuyCount.get(startGem);
if (startGemCount > 1) {
gemsToBuyCount.put(startGem, startGemCount - 1);
gemsToBuy.poll();
startIndex++;
} else {
break;
}
}
}
private void updateAnswer() {
if (gemsToBuyCount.size() == gemType.size() && answerSize > gemsToBuy.size()) {
answerStartIndex = startIndex;
answerSize = gemsToBuy.size();
}
}
}
참고
2차 풀이 (2021.05.04)
지난 번의 풀이와는 달리, 이번에는 투 포인터 기법을 사용해서 풀이했다. Queue에다 모든 보석을 저장할 필요 없이 두 개의 포인터로만 구간을 관리하는 방식을 적용해서 공간복잡도를 개선한 것이다.
효율성 살짝 부족한 코드
import java.util.*;
class Solution {
private int minStart = Integer.MAX_VALUE;
private int minSize = Integer.MAX_VALUE;
public int[] solution(String[] gems) {
Map<String, Integer> bucket = initBucket(gems);
findMinSection(gems, bucket);
return new int[]{minStart + 1, minStart + minSize};
}
private Map<String, Integer> initBucket(String[] gems) {
Map<String, Integer> bucket = new HashMap<>();
for (String gem : gems) bucket.putIfAbsent(gem, 0);
return bucket;
}
private void findMinSection(String[] gems, Map<String, Integer> bucket) {
int start = 0, end = 1;
bucket.put(gems[start], 1);
while (start < end) {
if (containsAllTypes(bucket)) {
int size = end - start;
if (size < minSize) {
minStart = start;
minSize = size;
}
bucket.put(gems[start], bucket.get(gems[start]) - 1);
start++;
} else {
if (end < gems.length) {
bucket.put(gems[end], bucket.get(gems[end]) + 1);
end++;
} else {
bucket.put(gems[start], bucket.get(gems[start]) - 1);
start++;
}
}
}
}
private boolean containsAllTypes(Map<String, Integer> bucket) {
for (int count : bucket.values())if (count < 1) return false;
return true;
}
}다른건 다 통과됐는데 효율성 검사의 마지막 5개 테케에서 시간초과가 떴다. containsAllTypes()에서 bucket를 처음부터 끝까지 다 탐색하기 때문이었던 것 같다.
정답 코드
그래서 HashMap 탐색하지 말고 숫자로 저장하도록 코드를 살짝 수정했더니, 코드는 살짝 더 더러워졌지만 실제 실행 시간도 확 줄고 모든 테케에서도 통과할 수 있었다.
import java.util.*;
class Solution {
private int minStart = Integer.MAX_VALUE;
private int minSize = Integer.MAX_VALUE;
public int[] solution(String[] gems) {
Map<String, Integer> bucket = initBucket(gems);
findMinSection(gems, bucket);
return new int[]{minStart + 1, minStart + minSize};
}
private Map<String, Integer> initBucket(String[] gems) {
Map<String, Integer> bucket = new HashMap<>();
for (String gem : gems) bucket.putIfAbsent(gem, 0);
return bucket;
}
private void findMinSection(String[] gems, Map<String, Integer> bucket) {
int start = 0, end = 1, typeCount = 1;
bucket.put(gems[start], 1);
while (start < end) {
if (typeCount == bucket.size()) {
int size = end - start;
if (size < minSize) {
minStart = start;
minSize = size;
}
bucket.put(gems[start], bucket.get(gems[start]) - 1);
if (bucket.get(gems[start]) < 1) typeCount--;
start++;
} else {
if (end < gems.length) {
bucket.put(gems[end], bucket.get(gems[end]) + 1);
if (bucket.get(gems[end]) == 1) typeCount++;
end++;
} else {
bucket.put(gems[start], bucket.get(gems[start]) - 1);
if (bucket.get(gems[start]) < 1) typeCount--;
start++;
}
}
}
}
}