[카카오 인턴] 보석 쇼핑

import java.util.*;
class Solution {
    public int[] solution(String[] gems) {
        int[] answer = new int[2];
        HashSet<String> set = new HashSet<String>();
        HashMap<String, Integer> map = new HashMap<String, Integer>();
        HashSet<String> collectedList = new HashSet<String>();
 
        // 보석 목록 저장
        for (int i = 0; i < gems.length; i++) {
            set.add(gems[i]);
        }
        // 보석 카운트 초기화
        for (String s : set)
            map.put(s, 0);
 
        int start = 0, end = 0;
        int left = 0, right = gems.length - 1;
        boolean flag = false;
        while (start < gems.length && end < gems.length) {
            // 수집되지 않은 상태
            if (!flag) {
                map.put(gems[end], map.get(gems[end]) + 1); // 현재 항목 추가
                collectedList.add(gems[end]);
            } else { // 수집된 상태
                map.put(gems[start - 1], map.get(gems[start - 1]) - 1); // 이전 항목 제거
                if (map.get(gems[start - 1]) == 0)
                    collectedList.remove(gems[start - 1]);
            }
 
            // 다 수집되었는지 확인
            if (collectedList.size() == set.size()) {
                flag = true;
                // 최소 구간 저장
                if (right - left > end - start) {
                    left = start;
                    right = end;
                }
                start++;
            } else {
                flag = false;
                end++;
            }
        }
        answer[0] = left + 1;
        answer[1] = right + 1;
        return answer;
    }
}

모든 보석을 수집하는 가장 최소 길이의 구간을 구하는 문제이다.

이중 for문을 사용하면 쉽게 해결할 수 있지만, 효율성의 문제로 인해 슬라이딩 윈도우 기법을 이용하였다.

해당 알고리즘은 이전에 계산했던 구간에 대한 처리를 제외하는 것으로 시간을 매우 절약할 수 있다.

 

보석이 수집되었는지 판단하는 것으로 매번 map의 모든 value를 검사했었는데, 이 때문에 시간 초과가 났다.

수집된 리스트를 Set으로 저장하고 해당 Set의 길이만 비교하는 것으로 해결하였다.

 

참고 사이트 1 : https://blog.fakecoding.com/archives/algorithm-slidingwindow/ 

참고 사이트 2 : https://m.blog.naver.com/kks227/220795165570