[pro] 프로그래머스 level3 67258 보석 쇼핑 (Java) - 투포인터

[문제]

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

프로그래머스

 

[풀이]

범위를 구하는 문제로, 투포인터를 이용해서 풀 수 있다.

1. 보석의 종류가 총 몇 가지인지 알기 위해 중복을 허용하지 않는 HashSet을 이용한다.

2. 포인터를 이동시켜가며 보석의 종류와 개수를 key, value로 저장하기 위해 HashMap을 이용한다.

3. left, right 변수를 이용해 투포인터를 이동시킨다. map의 size와 set의 사이즈가 일치하면 모든 종류의 보석을 다 담은 것이므로 가장 짧은 구간을 찾기 위해 left를 증가시킨다.  일치하지 않는다면 범위를 늘려야하기 때문에 right를 증가시킨다. 가장 짧은 구간을 찾기 위해 map의 size와 set의 사이즈가 일치하는 경우의 distance(= right-left)의 값이 작아질 수 있도록 갱신해주도록 한다. 

 

※ map.getOrDefault(Object key, Object defaultValue)를 사용하면 map에 해당 키가 존재하지 않을 경우 default value를 반환해준다.

 

[코드]

 

import java.util.*;

class Solution {
    public int[] solution(String[] gems) {
        int[] answer = new int[2];
        //모든 보석을 하나 이상 포함하는 가장 짧은 구간
        
        //보석 종류의 총 개수를 저장하기 위한 set
        Set<String> gemSet = new HashSet<>();
        Collections.addAll(gemSet, gems);
        
        //보석의 종류, 개수를 저장하기 위한 map
        Map<String, Integer> gemMap = new HashMap<>();
        
        int gemCnt = gemSet.size();
        int len = gems.length;
        
        int distance = Integer.MAX_VALUE; //right-left 저장
        int left = 0, right = 0; //투 포인터
        int start = 0, end = 0; //정답
        
        while(true){
            if(gemCnt == gemMap.size()){ //left 이동
                String leftGem = gems[left];
                gemMap.put(leftGem, gemMap.get(leftGem)-1);
                if(gemMap.get(leftGem)==0){
                    gemMap.remove(leftGem);
                }
                left++;
            }
            else if(right==len) break;
            else{ //right 이동
                String rightGem = gems[right];
                gemMap.put(rightGem, gemMap.getOrDefault(rightGem, 0)+1);
                right++;
            }
            
            if(gemCnt == gemMap.size()){
                //answer 갱신
                if(right-left < distance){
                    distance = right-left;
                    start = left+1;
                    end = right;
                }
            }
        }
        
        answer[0] = start;
        answer[1] = end;
        
        return answer;
    }
}