[프로그래머스] 보석 쇼핑 자바

문제

 

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

 

 

문제 풀이

 

✔️ 알고리즘

1. Set 자료구조를 이용하여 보석의 종류 개수를 구함.

2. gems배열을 편하게 카운팅 하기 위하여 HashMap으로 보석이름과 인덱스를 매칭해줌

3. gems배열을 순회하면서 모든 종류의 보석을 담았을 경우 인덱스 갱신해줌

 - sidx, eidx 둘 다 처음으로 지정한 후 모든 보석의 종류를 담을 때까지 eidx를 증가한다.

 - 이 때, 증가하면서 나온 보석들을 종류별로 카운팅해주는데 sidx를 다음 값으로 옮겼을 때, 같은 보석일 경우 바로 갱신을 해주고, 다른 보석일 경우에도 eidx의 보석값에 따라 바로 바로 값갱신이 가능해지기 때문

 

 

소스 코드

 

class Solution {
    public int[] solution(String[] gems) {
        int[] answer = new int[2];
        int idx = 1;
        HashMap<String, Integer> map = new HashMap<>();
        Set<String> set = new HashSet<>();
        
        for(String s: gems)
            set.add(s);
        
        for(String s: set)
            map.put(s, idx++);
        
        int num = set.size();   //보석 개수
        
        int min_idx = 0, max_idx = 0;
        int sidx = 0, eidx = 0;
        int[] count = new int[num+1];
        int cnt = 0, differ = Integer.MAX_VALUE;
        
        while(eidx < gems.length){
            if(count[map.get(gems[eidx])] == 0)
                cnt++;
            count[map.get(gems[eidx])]++;
            eidx++;
            
            while(cnt == num){
                if(differ > eidx - sidx){
                    differ = eidx - sidx;
                    max_idx = eidx;
                    min_idx = sidx;
                }
                count[map.get(gems[sidx])]--;
                if(count[map.get(gems[sidx])] == 0)
                    cnt--;
                sidx++;
            }
        }
        
        answer[0] = min_idx + 1;
        answer[1] = max_idx;
        return answer;
    }
}