문제

https://school.programmers.co.kr/learn/courses/30/lessons/67258

---

입력

진열대 번호 순서대로 보석들의 이름이 저장된 배열 gems

---

출력

모든 보석을 하나 이상 포함하는 가장 짧은 구간

---

풀이

제한조건

• gems 배열의 크기는 1 이상 100,000 이하입니다.
  • gems 배열의 각 원소는 진열대에 나열된 보석을 나타냅니다.
  • gems 배열에는 1번 진열대부터 진열대 번호 순서대로 보석이름이 차례대로 저장되어 있습니다.
  • gems 배열의 각 원소는 길이가 1 이상 10 이하인 알파벳 대문자로만 구성된 문자열입니다.

접근방법

친절하게 정확성 및 효율성 테스트가 존재한다고 적혀있다.
모든 경우의수를 살피면 안된다.

문제를 읽다보면, 슬라이딩 윈도우 투포인터와 관련된 문제라는걸 알 수 있다.

특정 구간을 스캔하며, 모든 종류의 보석이 1개 이상 존재하는지 그리고 가장 짧은 구간인지를 확인하면 된다.

1. 전체 보석의 종류를 계산
2. 왼쪽에서 오른쪽으로 진행하며, 진열대 번호를 하나씩 추가 시킨다.
3. 새로운 보석이 현재 범위에 들어왔다면, count를 증가시킨다.
4. count가 전체 보석의 종류 수와 같다면 왼쪽에서부터 제외될 수 있는 보석을 제외한다.
5. 구간을 비교한다.
6. 2~5과정을 반복한다.

---

코드

import java.util.*;

class Solution {
    public int[] solution(String[] gems) {
        Map<String, Integer> countMap = new HashMap();
        // 보석의 종류 파악 + Map에 0개로 기록
        for(String s : gems)
            countMap.computeIfAbsent(s, (k) -> 0);
        
        int numKinds = countMap.size();
        System.out.println(numKinds);
        
        int start = 0;
        int end = Integer.MAX_VALUE;
        int len = gems.length;
        int left = 0;
        int right = 0;
        int count = 0;
        for(right = 0 ; right < len; ++right){
            // 현재 맵에 0개로 넣어 놓았으므로, 항상 존재한다.
            int nums = countMap.get(gems[right]);
            
            // 해당 보석이 0개 였던 경우는 체크해야 한다.
            if(nums == 0){
                count++;
            }
            
            // 카운트만 증가.
            countMap.computeIfPresent(gems[right], (k, v) -> v + 1);
            
            while(true){
                int leftKeyCount = countMap.get(gems[left]);
                // 왼쪽 값이 1개 이상 존재한다면 제거해도 무방함.
                if(leftKeyCount > 1){
                    countMap.computeIfPresent(gems[left], (k, v) -> v - 1);
                    left++;
                } else {
                    break;
                }
            }
            
            // 구간의 길이 확인
            if(count == numKinds && right - left < end - start){
                start = left;
                end = right;
            }
        }
        
        return new int[] {start + 1, end + 1};
    }
}