Today I Learned
오늘은 슬라이딩 윈도우 문제를 검색해서 풀어봤는데 슬라이딩 윈도우 보다는 투포인터에 가깝게 문제를 풀었다. 효율성을 줄이기 힘든 문제였다.
보석 쇼핑
https://school.programmers.co.kr/learn/courses/30/lessons/67258
- 문제
카카오 인턴 출제. 배열 상 진열된 보석들 중 모든 종류의 보석을 포함하는 가장 짧은 부분 배열을 찾는 문제.
- 풀이 과정
-
부분 집합을 찾는 문제이기 때문에 이중 for문 보단 투포인터나 슬라이딩 윈도우를 사용하면 풀릴 것 같아보였다.
-
우선 주어진 배열에서 모든 종류의 보석을 추려내는 것을 해야했는데 이 과정은 set으로 구현했다. set은 중복 원소가 자동으로 걸러지므로
Set<String> set = new HaseSet<>(Arrays.asList(gems))로 배열(->리스트)->해시셋 으로 구현했다. set.size()로 몇 종류의 보석이 있는지 알 수 있다. -
부분 배열을 찾아야 되기 때문에 첫 시도는 슬라이딩 윈도우를 사용하려했다. 우선 보석의 종류만큼 window의 크기를 고정시켜두고 큐에 그 크기만큼 선입선출로 요소를 넣으면서 삭제해나가며 만족하는 경우를 찾아나갔다. 만약 해당 사이즈에서 찾지 못하면 window의 크기를 1씩 늘려가면서 while문으로 반복을 돌렸다.
하지만 이 방법은 효율성 테스트에서 좋은 결과가 나오지 않았다. 윈도우크기를 고정시켜서 한번순회하고 1씩 늘려가면서 계속 반복하기 때문이었다. -
그리고 위의 경우에선 중복되지않고 모든 종류가 다 있다는 걸 set을 다시 만들어 검증했었는데 비효율적이어서 해시맵을 써보기로했다. key는 보석의 종류로 하고 value를 부분배열 안에서 각 보석의 수를 넣는다. 바로 증가시키는 방법은 없으므로 getOrDefault()로 가져온 뒤 +1이나 -1하는 방식을 썼다. 그리고 최종적으로 map의 크기와 보석의 종류가 있는 set의 크기를 비교했을 때 같아지면 부분배열에 모든 종류의 보석이 다 있는 것이므로 답을 리턴한다.
-
고정된 슬라이딩 윈도우를 써야겠다는 생각을 버리고 다시 생각해봤다. 우선 투포인터를 써서 두 포인터 다 index 0에서 출발해서 조건을 만족할 때까지 right 포인터를 늘리고, 해당 조건이 맞는 한에서(while문의 조건) left 포인터를 늘려나가면 최소 크기의 배열이 된다.
-
left와 right를 +1해서 보정하여 return하면 끝.
- 구현 코드
import java.util.*;
class Solution {
public int[] solution(String[] gems) {
int[] answer = {1,gems.length};
Set<String> gemSet = new HashSet<>(Arrays.asList(gems));
Map<String, Integer> map = new HashMap<>();
int left = 0, right = 0;
int minLength = 100000;
while(right < gems.length){
int value = map.getOrDefault(gems[right],0);
map.put(gems[right], value+1);
while(map.size() == gemSet.size()){
if(right - left < minLength) {
minLength = right - left;
answer[0] = left;
answer[1] = right;
}
int s = map.get(gems[left]);
if(s==1) {
map.remove(gems[left]);
} else {
map.put(gems[left], s-1);
}
left++;
}
right++;
}
answer[0] += 1;
answer[1] += 1;
return answer;
}
}
