Programmers) 보석 쇼핑(Lv.3)

보석 쇼핑(2020 Kakao Internship)

문제풀이

"진열된 모든 종류의 보석을 적어도 1개 이상 포함하는 가장 짧은 구간을 찾아서 구매"

효율성 테스트도 있는 걸로 보아 이중 for문으로 접근하면 안되겠다 싶었다. 그래서 모든 종류의 보석을 포함하는 가장 짧은 구간을 탐색하기 위해 투포인터즈 알고리즘으로 접근하였다.

Two Pointers Algorithm
: 일차원 배열에서 두 개의 포인터를 이용해 원하는 값을 찾는 알고리즘

🤔 포함해야 할 보석의 종류?

우선은 모두 담아야 하는 보석의 종류가 무엇이 있는지 알아야 한다.
따라서 HashSet에 진열된 보석들(gems)을 set에 추가해주었다.

🤔 포인터 증감 조건

이제 gems를 탐색할 구간의 시작(left)과 끝(right)을 초기화한 뒤, 구간 증감 조건을 설정해보자.

일단은 보석을 담을 HashMap을 만들었다. 장바구니 역할로서, 보석의 종류를 key, 담긴 보석의 갯수를 value로 갖는다.

1. map에 보석을 담고 right를 늘려가면서 탐색구간을 넓힌다.

2. map의 key의 갯수와 set의 사이즈가 같아지면 모든 보석이 담겼다는 뜻이다! 이제 우리가 탐색할 수 있는 최대 범위가 정해졌다. 다시 포인터를 좁혀가면서 최소 간격을 추출해보자.

3. 시작이 끝을 넘어가지 않는 선에서,
만약 현재 시작 포인트(left)가 가리키는 인덱스의 보석의 value가 1 이상이라면 그 보석은 제외해도 좋다. map의 value를 1 줄이고 left 한 칸 이동해 간격을 좁혀준다.

3-1. 만약 보석이 1 이하라면 간격이 길이가 최소인지 확인해야 한다.
현재 탐색 길이(right - left)보다 이전 탐색 구간(distance)를 비교해서 현재 탐색 길이가 더 짧다면 distance를 재설정해주고, answer의 간격을 나타내는 값도 재설정해준다.

소스코드

import java.util.HashMap;
import java.util.HashSet;

class Solution {
    public int[] solution(String[] gems) {
        int[] answer = new int[2];
        // 보석 종류 탐색
        HashSet<String> set = new HashSet<>();
        for(String gem : gems) set.add(gem);
        // 담은 보석의 종류와 개수 세기
        HashMap<String, Integer> cart = new HashMap<>();

        int left = 0;
        int right = 0;
        int distance = gems.length + 1;

        while (right < gems.length) {
            cart.put(gems[right], cart.getOrDefault(gems[right], 0) + 1);
            right++;

            if (cart.size() == set.size()) {
                while (left < right) {
                    if (cart.get(gems[left]) > 1) {
                        cart.replace(gems[left], cart.get(gems[left]) - 1);
                        left += 1;
                    } else if (distance > (right - left)) {
                        distance = right - left;
                        answer[0] = left + 1;
                        answer[1] = right;
                        break;
                    } else break;
                }
            }
        }
        return answer;
    }
}