보석쇼핑

https://school.programmers.co.kr/learn/courses/30/lessons/67258

개발자 출신으로 세계 최고의 갑부가 된 어피치는 스트레스를 받을 때면 이를 풀기 위해 오프라인 매장에 쇼핑을 하러 가곤 합니다.
어피치는 쇼핑을 할 때면 매장 진열대의 특정 범위의 물건들을 모두 싹쓸이 구매하는 습관이 있습니다.
어느 날 스트레스를 풀기 위해 보석 매장에 쇼핑을 하러 간 어피치는 이전처럼 진열대의 특정 범위의 보석을 모두 구매하되 특별히 아래 목적을 달성하고 싶었습니다.
진열된 모든 종류의 보석을 적어도 1개 이상 포함하는 가장 짧은 구간을 찾아서 구매

예를 들어 아래 진열대는 4종류의 보석(RUBY, DIA, EMERALD, SAPPHIRE) 8개가 진열된 예시입니다.

가장 짧은 구간의 시작 진열대 번호와 끝 진열대 번호를 차례대로 배열에 담아서 return 하도록 하며, 만약 가장 짧은 구간이 여러 개라면 시작 진열대 번호가 가장 작은 구간을 return 합니다.

풀이 생각

1. 해당하는 문자열 배열을 만들어서 비교하자.
2. MAP에 한 번 들어왔던 친구들의 인덱스값을 가져가면 되지 않을까

소스코드

MAIN

public int[] solution(String[] gems) {

           int [] answer = new int [2];
    
        HashSet<String> set = new HashSet<>();
        HashMap<String,Integer> map = new HashMap<>();
        int len = gems.length;
        int distance = Integer.MAX_VALUE;
        for (int i = 0; i < len; i++) {
            set.add(gems[i]);
        }
        
        int left=0;
        int right=0;


        int start =0;
        int end = 0;

        while(left <= right){
        //set 에 포함되어 있는 1번 짜리 문자열의 map
        if(set.size() == map.size()){
            map.put(gems[left],map.get(gems[left])-1);
            if(map.get(gems[left])==0){
                // 들어 온적있니?
                map.remove(gems[left]);
                //아끝까지 돌고 이제 start줄일 차례네
            }
            left++;
        }else if(right == len){
            break;
        }else{
            //이제 end로 순차적 이동
           
                map.put(gems[right], map.getOrDefault(gems[right],0)+1);
            right++;
            
        }

        if(map.size() == set.size()){
            if(right-left < distance){
                distance = right - left;
                start = left+1;
                end = right;
            }
        }
        }

        answer[0]= start;
        answer[1] = end;
        
        return answer;
    }

Queue & HashMap 사용

    public static void main(String[] args) {

        String [] gems ={"AA", "AB", "AC", "AA", "AC"};
        int [] result= new int[2];
        Map<String, Integer> map = new HashMap<>();
        Set<String> set = new HashSet<>();
        Queue<String> queue = new LinkedList<>();

        int len = Integer.MAX_VALUE, start = 0, idx = 0;

        set.addAll(Arrays.asList(gems));

        for (int i = 0; i < gems.length; i++) {
            map.put(gems[i], map.getOrDefault(gems[i], 0) + 1);
            queue.add(gems[i]);

            while (map.get(queue.peek()) > 1) {
                map.put(queue.peek(), map.get(queue.poll()) - 1);
                idx++;
            }

            if (map.size() == set.size() && len > (i - idx)) {
                len = i - idx;
                start = idx + 1;
            }
        }
        result[0]= start;
        result[1]= start+len;
        System.out.println(Arrays.toString(result));
    }

공부할 것

관련문제 몇 번더 풀어볼 것 , 프로그래머스 문제 풀이

참고

https://girawhale.tistory.com/85