[Programmers] 보석 쇼핑

2020 카카오 인턴십 문제로 투 포인터 알고리즘 문제이다.

 

[문제 정답]

import java.util.*;

class Solution {

    public int[] solution(String[] gems) {
        int[] answer = new int[2];

        HashSet<String> gemSet = new HashSet<>();
        gemSet.addAll(Arrays.asList(gems));
        int typeNum = gemSet.size();
        
        int start = 0;
        int end = 0;
        
        int gemsNum = gems.length;
        int distance = Integer.MAX_VALUE;
        int distanceIndex = Integer.MAX_VALUE;
        
        HashMap<String, Integer> gemMap = new HashMap<>();
        gemMap.put(gems[0], 1);
        while(start < gemsNum && end < gemsNum) {
            //System.out.println("start : " + start + " end : " + end);
            //System.out.println("gemMap.size() : " + gemMap.size() + " gemSet.size() : " + gemSet.size());
            /* 포인터들의 이동으로 정답 조건이 되었을 경우 */
            if(gemMap.size() == gemSet.size()) { 
                /* 답 갱신 */
                /* 가장 짧은 구간이면서 시작 진열대 번호가 가장 작은 구간이 정답 */
                /* 어차피 작은 인덱스에서 순차적으로 실행되기 때문에 같은 구간이라면 인덱스 검사 안 해도 됨 */
                if (distance > end-start) {
                    distance = end-start;
                    answer[0] = start+1;
                    answer[1] = end+1;
                }
                /* start 포인터 지점과 관련한 변수 계산 부분 초기화 */
                gemMap.put(gems[start], gemMap.getOrDefault(gems[start],0) - 1);
                /* 값을 빼서 언더플로우가 되었을 때를 대비한 예외 처리 */
                if(gemMap.get(gems[start]) <= 0)
                    gemMap.remove(gems[start]);
                /* start 포인터 증가 */
                start++;
            } else {
                /* 포인터들의 이동으로 정답 조건이 되지 않았을 경우 */
                /* end 포인터 증가 */
                end++;
                if (end == gemsNum)
                    break;
                /* end 포인터 지점과 관련한 변수 계산 부분 업데이트 */
                gemMap.put(gems[end], gemMap.getOrDefault(gems[end], 0) + 1);
            }
            //System.out.println("after gemMap size : " + gemMap.size());
        }
        return answer;
    }
    
}