[Programmers / Level 3] 67258. [카카오 인턴] 보석 쇼핑 (Java)

💡 Info

• 난이도: Lv3
  프로그래머스 링크: https://school.programmers.co.kr/learn/courses/30/lessons/67258
  풀이 링크(GitHub): hayannn/CodingTest_Java/프로그래머스/3/[카카오 인턴] 보석 쇼핑

입출력 조건

입출력 예시

문제 이해

• 모든 종류의 보석을 포함하는 가장 짧은 구간 찾기

알고리즘

풀이 시간 : 16분

• 슬라이딩 윈도우(left, right)
• right 포인터로 윈도우 확장하면서 보석을 map에 카운팅
• map.size()가 전체 보석 종류 개수와 같아지면 -> 모든 보석 포함
• left 이동
• 최소 구간 길이 -> 갱신

import java.util.*;

class Solution {
    public int[] solution(String[] gems) {
        int totalKinds = new HashSet<>(Arrays.asList(gems)).size();
        Map<String, Integer> map = new HashMap<>();
        int left = 0, right = 0;
        int minLen = Integer.MAX_VALUE;
        int[] answer = new int[2];

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

            while (map.size() == totalKinds) {
                if (right - left < minLen) {
                    minLen = right - left;
                    answer[0] = left + 1;
                    answer[1] = right;
                }

                map.put(gems[left], map.get(gems[left]) - 1);
                if (map.get(gems[left]) == 0) {
                    map.remove(gems[left]);
                }
                left++;
            }
        }

        return answer;
    }
}

결과