프로그래머스 - 보석 쇼핑

Java

보석 쇼핑

문제

접근 방법

1. 담아야할 보석 종류의 개수를 SET을 통해 센다.
2. 2개의 포인터 (start, end)를 통해 보석을 담고/제거한다.
   • start : 보석을 제거하는 담당
   • end : 보석을 추가하는 담당
3. end로 시작점 부터 이동하며, 보석을 담는다 map.put(gems[end], map.getOrDefault(gems[end], 0) + 1);
4. 해당 목표는 최대한 중복없이 짧은 거리의 보석 구간을 찾아야하므로, end가 보석을 담을 때 마다 start로 보석을 제거한다(중복이 있을 시)

   while(map.get(gems[start]) > 1) { 
    map.put(gems[start], map.get(gems[start]) - 1); 
    start++; 
   }
   

5. 모든 보석을 포함했는지 확인하여, start end 사이 최단거리를 추출한다.

코드

import java.util.*;

class Solution {
    public int[] solution(String[] gems) {
        int[] answer = {};
        
        int n = gems.length;
        int needSize = new HashSet<String>(Arrays.asList(gems)).size();
        
        int start = 0, end = 0;
        int len = Integer.MAX_VALUE;
        int shortS = 0, shortE = 0;
        Map<String, Integer> map = new HashMap<>();
        // 보석을 하나씩 담는다
        while(end < n) {
            map.put(gems[end], map.getOrDefault(gems[end], 0) + 1);
            
            // End가 이동하면서 담은 보석 중 중복이 쌓였으면 제거한다.
            while(map.get(gems[start]) > 1) {
                map.put(gems[start], map.get(gems[start]) - 1);
                start++;
            }
            
            // 만약 목표하는 보석의 종류만큼 담았으면, start / end 사이 거리가 가장 짧은 거리 도출
            if(map.size() == needSize && len > end - start) {
                len = end - start;
                shortS = start + 1;
                shortE = end + 1;
            }

            end++;
        }
        answer = new int[] {shortS, shortE};
        return answer;
    }
}