[ 프로그래머스 ] 67258 보석 쇼핑

📌 Problem

일렬로 진열된 보석들이 String 배열로 주어진다. 보석 진열대에서 최소한의 연속된 보석들을 구매하여 모든 종류의 보석들을 최소 1개씩을 구매하고자 한다. 최소한의 길이를 가진 경우에서 시작 번호와 끝 번호를 배열로 반환해라. 보석은 주어진 배열의 index 0부터 1번이라고 생각한다. 또한 최소 길이가 동일한 경우에는 시작 번호가 작은 경우를 선택한다.

📌 Solution

2 Pointer으로 해결할 수 있는 문제이다. 첫 번째 보석부터 차례대로 탐색하며 다음의 과적을 진행한다.

Step 1. 선택한 보석을 구매 바구니에 담는다. (바구니는 담은 순서를 기억한다.)
Step 2. 첫 번째로 바구니에 담은 보석부터 탐색한다.
	Step 2-1. 만약 같은 종류의 보석이 2개 이상이면 해당 보석을 바구니에서 뺀다.
    Step 2-2. 만약 같은 종류의 보석이 없으면 더는 보석을 제외하지 않는다. (To Step 3)
Step 3. 바구니에 담긴 보석들이 전체 보석 종류를 하나씩 담고 있다면 해당 정보를 저장한다.
	Step 3-1. 만약 저장한 정보에서 보석 선택 길이가 이전보다 작다면 해당 정보로 업데이트한다.

📌 Example

["DIA", "RUBY", "RUBY", "DIA", "DIA", "EMERALD", "SAPPHIRE", "DIA"]

1. DIA (Basket : DIA)
	- 바구니에 DIA를 담는다.
    - 제외할 보석이 없으며 모든 종류를 담지 않았기 때문에 다음으로 넘어간다.
2. RUBY (Basket : DIA, RUBY)
	- 바구니에 RUBY를 담는다.
    - 제외할 보석이 없으며 모든 종류를 담지 않았기 때문에 다음으로 넘어간다.
3. RUBY (Basket : DIA, RUBY, RUBY)
	- 바구니에 RUBY를 담는다.
    - 제외할 보석이 없으며 모든 종류를 담지 않았기 때문에 다음으로 넘어간다.
4. DIA (Basket : DIA, RUBY, RUBY, DIA → RUBY, DIA)
	- 바구니에 DIA를 담는다.
    - 첫 번째 보석인 DIA가 중복되므로 제외한다. (RUBY, RUBY, DIA)
    - 두 번쨰 보석인 RUBY가 중복되므로 제외한다. (RUBY, DIA)
    - 모든 종류를 담지 않았기 때문에 다음으로 넘어간다.
5. DIA (Basket : RUBY, DIA, DIA)
	- 바구니에 DIA를 담는다.
    - 제외할 보석이 없으며 모든 종류를 담지 않았기 때문에 다음으로 넘어간다.
6. EMERALD (Basket : RUBY, DIA, DIA, EMERALD)
	- 바구니에 EMERALD를 담는다.
    - 제외할 보석이 없으며 모든 종류를 담지 않았기 때문에 다음으로 넘어간다.
7. SAPPHIRE (Basket : RUBY, DIA, DIA, EMERALD, SAPPHIRE)
	- 바구니에 SAPPHIRE를 담는다.
    - 제외할 보석이 없다.
    - 모든 종류의 보석을 담은은 경우이다. (길이 : 5 시작 : 3 끝 : 7)
8. DIA (Basket : RUBY, DIA, DIA, EMERALD, SAPPHIRE, DIA)
	- 바구니에 DIA를 담는다.
    - 제외할 보석이 없다.
    - 모든 종류의 보석을 담은 경우이다. (길이 : 6 시작 : 3 끝 : 8)

RESULT. 모든 종류의 보석을 담은 경우 중 가장 짧고 시작 번호가 작은 [3, 7]을 선택한다.

📌 Code

class Solution {
    public int[] solution(String[] gems) {
        Set<String> category = Arrays.stream(gems).collect(Collectors.toSet());

        int minLength = 100_001, start = 0, end = 0;

        Map<String, Integer> basket = new HashMap<>();

        int from = 1, to;
        for (int g = 1; g <= gems.length; g++) {
            to = g;
            basket.merge(gems[to - 1], 1, Integer::sum);
            while (basket.getOrDefault(gems[from - 1], 0) > 1)
                basket.merge(gems[from++ - 1], -1, Integer::sum);
            if (basket.keySet().size() == category.size() && to - from + 1 < minLength)
                minLength = (end = to) - (start = from) + 1;
        }

        return new int[]{start, end};
    }
}