> 문제
문제 : [보석 쇼핑]
> 문제풀이
- 보석 갯수를 Set으로 구한다. 이를 Size라고 한다.
- 인덱스 0부터 탐색을 시작한다.
- Size만큼의 보석을 찾았을 때를 기점(tmpE)으로 반대로 다시 탐색한다.
- 다시 Size만큼 보석을 찾았을 때(tmpS)가 모든 보석을 포함하는 범위가 된다.
- 하지만 최소의 범위가 아니기 때문에 tmpS+1부터 탐색을 반복한다.
투포인트 방식으로 풀지 않았기 때문에 시간은 상대적으로 조금 더 걸리는 듯 하다.
import java.util.*;
class Solution {
public int[] solution(String[] gems) {
Set<String> set = new HashSet<>();
for(int i=0; i<gems.length; i++){
set.add(gems[i]);
}
int size = set.size();
Set<String> tmpSet = new HashSet<>();
int length = Integer.MAX_VALUE;
int start = 0, end = gems.length-1;
for(int i=0; i<gems.length; i++){
tmpSet.add(gems[i]);
int tmpS = 0, tmpE = gems.length-1;
if(tmpSet.size() == size){
tmpE = i;
tmpSet = new HashSet<>();
int tmp = 0;
for(int j=tmpE; j>=0; j--){
tmpSet.add(gems[j]);
tmp++;
if(tmpSet.size() == size){
tmpS = j;
if(length > tmp) {
length = tmp;
start = tmpS;
end = tmpE;
}
tmpSet = new HashSet<>();
i=tmpS;
break;
}
}
}
}
return new int[]{start+1, end+1};
}
}
문제 출처 : Programmers