보석 쇼핑
문제
https://school.programmers.co.kr/learn/courses/30/lessons/67258
풀이
우선은 간단하게,,
보석들의 종류 개수를 구하고, 구역을 넓혀가면서 모든 보석을 포함하는 최소 구역을 찾는 브루트 포스 기법을 생각하였는데,
음 다시 잘 생각해보자
반복문을 최소로 돌리기 위해서는
계속해서 새로운 구역을 생성하는 것이 아닌 시작과 끝만 잘 이동해주면 된다.
예를 들어서
처음에 "보석1"이 나왔는데 뒤에서 "보석1"을 이미 포함하고 있다면?!
처음에 나온 "보석1"은 제외해도 된다는 것이다.
하지만 만약 뒤에서 "보석1"을 포함하고 있지 않다면 ?!
그때는 처음에 나온 "보석1"을 제외하지 못하니,
처음(1)부터 어디까지 끝을 맺어야 영역의 길이가 최소이면서 모든 보석을 포함하는지를 찾아야 한다.
예제 1
gems = ["DIA", "RUBY", "RUBY", "DIA", "DIA", "EMERALD", "SAPPHIRE", "DIA"]
우선 끝(end)가 배열을 돌면서 보석을 수집하면서 Map에다가 개수를 저장한다.
동시에 항상 시작(start)가 자신이 위치해있는 보석의 개수가 1개 이상인지를 체크한다.
start=0, end=0
{"DIA" : 1}
start=0, end=1
{"DIA" : 1, "RUBY" : 1}
start=0, end=2
{"DIA" : 1, "RUBY" : 2}
start=0, end=3
{"DIA" : 2, "RUBY" : 2}인데.. 여기서 시작(start)에 위치해있는 "DIA"가 1개 이상이다. (2개!)
그럼 이때 "DIA"가 뒤에 포함되어 있다는 것이니 처음에 나온 "DIA"는 제외한다. (-1)
따라서 start를 하나 앞으로 옮긴다.
start=1, end=4 (4번째 보석이 "DIA"이니 "DIA"에 하나를 올려준다)
{"DIA" : 2, "RUBY" : 2}이때도, 시작(start)에 위치해있는 "RUBY"가 1개 이상이므로 여기서도 앞에 나온 "RUBY"는 제외한다.
또 start를 하나 앞으로 옮긴다.
start=2, end=5
{"DIA" : 2, "RUBY" : 1, "EMERALD" : 1}
start=2, end=6
{"DIA" : 2, "RUBY" : 1, "EMERALD" : 1, "SAPPHIRE" : 1}여기서 잠깐!
보석들을 확인해보면 모든 종류의 보석들이 모두 포함되어 있는 것을 확인할 수 있다.
따라서 해당 영역의 길이가 제일 짧은지 비교하여 업데이트 한다.
SIZE = 6-2 = 4, 영역 = [3,7] (인덱스에서 +1을 해준 값)
start=2, end=7
{"DIA" : 3, "RUBY" : 1, "EMERALD" : 1, "SAPPHIRE" : 1}여기서도 보석들이 모두 포함되어 있지만, 해당 영역의 길이가 7-2=5로 전에 더 짧은 영역(4)가 존재하므로 패스된다.
따라서 결론적으로는 [3,7]이 반환된다.
예제 2
gems = ["AA", "AB", "AC", "AA", "AC"]
start=0, end=0
{"AA" : 1}
start=0, end=1
{"AA" : 1, "AB" : 1}
start=0, end=2
{"AA" : 1, "AB" : 1, "AC" : 1}모든 보석들을 포함하고 있기 때문에,
SIZE = 2-0 = 2, 영역 = [1,3]
start=0, end=3
{"AA" : 2, "AB" : 1, "AC" : 1}시작(start)에 위치한 보석 "AA"가 1개 이상이므로 처음에 나온 "AA" 제외
start가 하나 올라간 상황에서
start=1, end=3
{"AA" : 1, "AB" : 1, "AC" : 1}SIZE가 3-1=2로 기존과 동일하므로 패스
start=1, end=4
{"AA" : 1, "AB" : 1, "AC" : 2}모든 보석들을 포함하고 있지만, SIZE=4-1=3으로 기존의 SIZE보다 크므로 패스
결론적으로 [1,3]이 반환된다.
코드
import java.util.*;
class Solution {
public int SIZE = 100000; //영역의 크기 초기화
public int[] solution(String[] gems){
int len = new HashSet<>(Arrays.asList(gems)).size(); //보석들의 종류 개수
Map<String, Integer> sequence = new HashMap<>(); //보석들의 개수를 차곡히 쌓을 Map
int [] answer = new int[2];
int start = 0; //시작
for (int end=0; end<gems.length; end++){ //끝지점부터 먼저 하나씩 올린다.
sequence.put(gems[end], sequence.getOrDefault(gems[end], 0) + 1); //만약 보석이 없으면 0, 있다면 기존에 있던 값에서 +1 업데이트한다.
//만약 start에 위치해있는 보석이 2개 이상이 되면 앞에 나온 보석은 제외한다.
while (sequence.get(gems[start]) > 1){
sequence.put(gems[start], sequence.get(gems[start]) -1);
start ++; //그리고 시작점을 하나 앞으로 옮긴다.
}
//보석들의 종류가 모두 존재하고, SIZE가 최솟값이라면 업데이트
if (sequence.size() == len && (end - start) < SIZE){
SIZE = end - start;
answer[0] = start+1;
answer[1] = end+1;
}
}
return answer;
}
}