프로그래머스 - 보석 쇼핑

해당 문제는 투포인트 알고리즘을 통해 풀었다. 

 

투포인트 알고리즘이란 이중 포문을 통해서 구해야하는 공식을 왼쪽 끝, 오른쪽 끝 양끝점을 기준으로 조금씩 좁혀오며 범위를 계산해주어 푸는 문제이다. 

아래 문제같은 경우에도 겹치는 최소부분을 구하기 위해 양쪽 끝을 기준으로 겹치지 않는 보석이 있을 때까지 범위를 좁혀주어 HashSet에 들어가있는 보석의 개수 크기만큼 종류의 개수를 구해주어 문제를 해결하는 방식으로 구현하였다. 

import java.util.*;

class Solution {
    public int[] solution(String[] gems) {
        
        int kind = new HashSet<>(Arrays.asList(gems)).size();
        
        int[] answer = new int[2];
        int length = Integer.MAX_VALUE, start = 0;
        
        Map<String, Integer> map = new HashMap<>();
        
        for(int end = 0; end < gems.length; end++) {
            map.put(gems[end], map.getOrDefault(gems[end], 0) + 1);
            
            while(map.get(gems[start]) > 1) {
                map.put(gems[start], map.get(gems[start])-1);
                start++;
            }
            
            if(map.size() == kind && length > (end - start)) {
                length = end - start;
                answer[0] = start + 1;
                answer[1] = end + 1;
            }
            
        }
        
        
        return answer;
    }
}