이번에 풀어본 문제는
프로그래머스 보석 쇼핑 입니다.

📕 문제 링크

❗️코드

import java.util.*;
class Solution {
    public int[] solution(String[] gems) {
        Set<String> set = new HashSet<>(Arrays.asList(gems));
        Map<String, Integer> hm = new HashMap<>();
        Queue<String> q = new LinkedList<>();
        
        int start = 0;
        int len = Integer.MAX_VALUE;
        int tmpStart = 1;
        for (String gem : gems) {
            hm.put(gem, hm.getOrDefault(gem, 0) + 1);

            q.add(gem);

            while (true) {
                // 중복 제거
                String oldGem = q.peek();
                // 두개 이상이면
                if (hm.get(oldGem) > 1) {
                    // 값 줄이고 목록에서 제거, start++
                    hm.put(oldGem, hm.get(oldGem) - 1);
                    q.poll();
                    tmpStart++;
                }
                else break;
            }

            // 보석 종류의 개수가 같고, 이전보다 길이가 짧을 때
            if (hm.size() == set.size() && q.size() < len) {
                start = tmpStart;
                len = q.size();
            }
        }

        return new int[]{start, start + len - 1};
    }
}

📝 풀이

특정 구간의 보석을 일괄적으로 구매한다고 할 때, 가장 짧은 길이로 모든 보석을 포함시키는 인덱스를 반환하는 문제입니다.
모든 보석의 종류를 담을 Set, 현재 선택한 진열대의 범위 내에서 포함한 보석의 개수를 담은 Map(key = 보석, value = 포함개수), 마지막으로 현재 진열대의 현황을 담은 Queue로 총 3가지 자료구조를 활용합니다.
중복된 보석이 발생했을 경우, 가장 이전에 담았던 보석부터 제거해야 하므로, 큐의 최상단 값을 확인하여, 현재 Map의 value가 2이상이라면 앞쪽의 보석부터 하나씩 제거해줍니다.
해당 과정을 반복하다가, Set과 크기가 같아지는 시점에서 현재 진열대의 인덱스를 저장해주면 됩니다. 하지만, 이전보다 길이가 긴 진열대는 고려할 필요가 없으므로, 현재 Queue의 크기보다 이전에 누적된 len의 값이 클 경우에만 갱신해줍니다.

📜 후기

자료구조는 잘 활용한다고 생각했는데, 좀 어려웠던 문제입니다 ㅠ