프로그래머스 - 보석 쇼핑 문제 (자바)

programmers.co.kr/learn/courses/30/lessons/67258

코딩테스트 연습 - 보석 쇼핑

구간을 큐로 만들고

구간에 포함된 보석을 map으로 하여 1보다 작아지지 않게 하면서 

구간을 늘리고 이동시키면서 해결하면 된다.

 

핵심으로는

구간을 늘리며 보석을 추가한 뒤

구간의 맨 앞에 있는 보석이 2개 이상인 경우 맨 앞의 보석을 구간에서 제거하는 일을 반복한다.

제거할때 마다 구간의 시작 지점이 +1 되는 것으로 해당 값을 변경한다.

구간 정리가 끝나면 map에 추가된 보석의 종류와 전체 보석의 종류가 동일하면서

구간의 길이가 더 짧은 경우 시작지점과 구간의 길이를 초기화 해준다.

여기서 더 짧은 경우만 하는 이유는

동일한 길이를 가진다면 시작 진영대 번호가 가장 작은 구간을 리턴해야 하기 때문에 더 짧지 않다면 초기화 하지않는 것이다.

import java.util.*;

class Solution {
    public int[] solution(String[] gems) {
        HashMap<String, Integer> hashMap = new HashMap<>();
        HashSet<String> hashSet = new HashSet<>(Arrays.asList(gems));
        Queue<String> interval = new LinkedList<>();
        int length = Integer.MAX_VALUE;
        int intervalStart = 0; // 구간 시작 지점
        int tempIntervalStart = 0; // 계산용 구간 시작 지점
        
        for(int i = 0; i < gems.length; i++) {
            String gemName = gems[i];

            // 구간에 늘리며 보석 추가
            hashMap.put(gemName, hashMap.getOrDefault(gemName, 0) + 1);
            interval.offer(gemName);

            while(true) {
                String temp = interval.peek(); // 구간 첫번째 보석

                // 구간 첫번째 보석이 2개 이상인 경우
                if (hashMap.get(temp) > 1) {
                    // 구간 첫번째 보석을 제거
                    hashMap.put(temp, hashMap.get(temp) - 1);
                    interval.poll();

                    // 구간시작지점을 다음 지점으로 변경
                    tempIntervalStart++;
                }else {
                    break;
                }
            }

            // 구간에 등록된 보석 종류의 수와 전체 보석 종류 수가 같으며
            // 이전에 해당 조건을 충족한 구간의 길이보다 짧은 경우
            if(hashMap.size() == hashSet.size() && length > interval.size()) {
                length = interval.size();
                intervalStart = tempIntervalStart;
            }
        }

        return new int[]{intervalStart + 1, intervalStart + length};
    }
}