[프로그래머스_2020카카오인턴십]보석쇼핑

• 50분걸림
• 특정범위의 보석을 모두 구매하되, 특별한 목적을 달성하고 싶다.
  • 진열된 "모든 종류의 보석"을 "적어도 1개 이상"포함하는 "가장 짧은 구간"을 찾아서 구매
  • "연속된 구간"이어야 한다.
• 구해야 하는 것 : "모든 보석을 하나 이상 포함" 하는 "가장 짧은 구간"을 리턴하기. → "가장짧은 구간"의 "시작 진열대 번호"와 "끝 진열대 번호"를 배열에 담아 return하기
• 만약 가장짧은 구간이 "여러 개 " 라면 , "시작 진열대 번호"가 가장 작은 구간을 리턴하기

문제 풀이

• 문제에서 다시 한번 "연속된 구간임"을 강조하고 있다.
• Sliding window 와 Hash를 사용해야 할 것 같다.
• String[] gems만이 주어진다 → 따라서 "모든 종류의 보석"을 알기 위해서, 먼저 gems를 한 번 순회해야 한다.
  • → HashSet? HashMap 으로 ?
  • HashMap으로 1을 세팅해 두도록 한다. window를 expand하고 shrink하면서
    • expand할 때는, 이 HashMap에 있는 원소면, Map에서 remove를 한다.
    • shrink할 때는, 이 HashMap에 원소를 복귀시킨다.
• "가장 작은 구간"?
  • Sliding window로 푼다면, 이 window를 expand시키거나 move 시켜야 하는데, 그 기준을 어떻게 할 것인가.
    • "중복"되는 것이 등장한다고, window를 이동시키면 안되니까.. 어떻게 해야할지 고민이 된다.
    • 아 일단,일반적인 Sliding WIndow방식을 생각하면
      • 먼저, 모든 보석이 Window에 다 포함될 때 까지 exapnd를 시킨다.
      • 모든 보석이 Window에 다 포함된 순간 → shrink를 하기 시작한다.
      • shrink를 하여 모든 보석이 window에 다 포함이 되지 않게 된다면, Window를 exapnd한다.
      • 이를 반복하며, 다 포함 될 때 마다의 window 길이를 min과 비교하며 update한다.
  • HashSet 에 모든 종류의 보석을 담는다.
  • HashMap에 현재 윈도우의 정보를 담는다.
  • 따라서 현재의 window가 모든 보석을 cover하는 가는, Set의 size와 Map의 size를 비교하여 → 같은 경우, 모든 보석을 cover하는 것이다.

    import java.util.*;

    public class Main {

        public static int[] solution(String[] gems) {
            int[] answer = new int[2];
            int min = Integer.MAX_VALUE;
            HashSet<String> set = new HashSet<>();
            HashMap<String,Integer> map = new HashMap<>();
            // 모든 종류의 보석을 set에 넣는다. 
            // setting map
            for (String gem : gems) {
                set.add(gem);
            }
            // Sliding Window -> gems.length <=100,000
            int windStart =0,windEnd=0;
            int add=0,del=0;
            for(windEnd=0;windEnd<gems.length;windEnd++){
                //expand : add this element into the map (while expanding)
                add = map.getOrDefault(gems[windEnd],0);
                map.put(gems[windEnd],add+1);
                // after adding, check whether this window cover every kinds of 보석
                while(map.size()==set.size()){
                    // length update
                    if(min > (windEnd-windStart+1)) {
                        min = windEnd-windStart+1;
                        answer[0]= windStart+1;
                        answer[1]= windEnd+1;
                    }
                    // shrink
                    del = map.get(gems[windStart])-1;
                    map.put(gems[windStart],del);
                    if(map.get(gems[windStart])==0) map.remove(gems[windStart]);
                    windStart++;
                }
            }
            return answer;
        }

        public static void main(String[] args) {
            String[][] test = {{"AA", "AB", "AC", "AA", "AC"},{"DIA", "RUBY", "RUBY", "DIA", "DIA", "EMERALD", "SAPPHIRE", "DIA"},
                    {"XYZ", "XYZ", "XYZ"},{"ZZZ", "YYY", "NNNN", "YYY", "BBB"},{"aa"},{"aa","aa"}};
            for (String[] strings : test) {
                int[] res = solution(strings);
                System.out.println("=================RESULT=================");
                System.out.println(res[0]+","+res[1]);
                System.out.println("=================END=================");
            }
        }
    }
    ```