[프로그래머스] 보석 쇼핑 - JAVA

문제링크 🚩

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

프로그래머스

​

📕 문제 접근 📕

해당 문제 해결을 위해 다음과 같은 조건을 만족해야 한다.

1. 모든 보석을 구매해야한다. 

2. 모든 보석을 구매하며 가장 짧은 구간을 찾아야 한다. 

 

1번 조건을 해결하기 위해 보석의 총 개수를 Set를 통하여 구하며 Map을 사용하여 보석을 Key로 지정하여 gemsSize와 동일한지 비교한다.

int gemsSize = allGems.size();

Map<String, Integer> gemsMap = new HashMap<>();

gemsMap.size() == gemsSize // 다음과 같은 조건이 만족된다면 1번 조건을 만족함.

 

 

2번 조건을 만족하기 위해서는 구간을 줄여나가는 것이 중요함. 1번 조건을 만족하는 상태에서 시작 지점을 점차 키워나간다면 가장 짧은 구간의 Start 지점을 찾을 수 있다.

 

즉, 슬라이딩 윈도우를 사용한다면 문제를 해결할 수 있다.

 

코드는 아래와 같다. 

 

 

💻 Code 💻

import java.util.*;

class Solution {
    public int[] solution(String[] gems) {
        int[] answer = {};
        Set<String> allGems = new HashSet<>(Arrays.asList(gems));
        
        Map<String, Integer> gemsMap = new HashMap<>();
        
        
        int gemsSize = allGems.size();
        int minLength = Integer.MAX_VALUE;
        int start = 0, end = 0;
        int startIndex = 0;
        
        while(end < gems.length){
           
            gemsMap.put(gems[end], gemsMap.getOrDefault(gems[end], 0) + 1);
            end++;
            
            while(gemsMap.size() == gemsSize){
                if(end - start < minLength){
                    minLength = end - start;
                    startIndex = start;  
                }
                
                gemsMap.put(gems[start], gemsMap.get(gems[start]) -1);
                if(gemsMap.get(gems[start]) == 0 ){
                    gemsMap.remove(gems[start]);
                }
                start++;
            }
            
            
        }
        
        return new int[]{startIndex + 1, startIndex + minLength};
    }
}