[프로그래머스] [카카오 인턴] 보석 쇼핑(67258)

1. 문제 풀이 아이디어

• Set을 사용해 보석의 모든 종류 수를 구하고, Map과 두 포인터를 활용해 원하는 구간을 찾아 문제를 해결할 수 있다.

2. 나의 정답 코드

class Solution {
    public int[] solution(String[] gems) {
        int size = new HashSet<String>(Arrays.asList(gems)).size();
        int l = 0;
        int r = 0;
        int ll = 0;
        int rr = Integer.MAX_VALUE;
        Map<String, Integer> map = new HashMap<>();
        map.put(gems[0], 1);
        while (r < gems.length && l <= r) {
            if (r - l + 1 < size || map.size() < size) {
                r++;
                if (r < gems.length)
                    map.put(gems[r], map.getOrDefault(gems[r], 0) + 1);
            } else {
                if (r - l < rr - ll) {
                    rr = r;
                    ll = l;
                }
                map.put(gems[l], map.get(gems[l]) - 1);
                if (map.get(gems[l]) == 0) {
                    map.remove(gems[l]);
                }
                l++;
            }
        }
        return new int[]{ll + 1, rr + 1};
    }
}

3. 정리

• HashSet을 사용해 gems 배열에서 보석의 종류 개수를 구하고, 이를 size에 저장한다.

• 두 포인터 l과 r을 초기화하고, 최소 구간을 저장할 ll과 rr을 초기화한다.

• 구간 내 보석 정보를 저장할 map을 초기화하고, 첫 번째 보석을 추가한다.

• r이 gems의 길이보다 작고, l이 r 이하일 때 반복문을 실행한다.
• 구간의 크기가 size보다 작거나, map의 크기가 size보다 작으면 r을 증가시키고 map에 r번째 값을 추가한다.
• 그렇지 않을 경우, 저장된 최소 구간(rr, ll)보다 현재 구간(r, l)이 더 작으면 갱신하고, map에서 l번째 값을 감소시키고, 값이 0이 되면 제거한 뒤 l을 증가시킨다.

• 반복이 끝난 후, 최종 구간 ll과 rr에 1을 더해 반환한다.