[프로그래머스] 보석 쇼핑 / 2020 카카오 인턴십 - JAVA

🔗 문제 링크

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

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

 

📝 풀이 과정

Set에 중복이 되지 않도록 모든 보석을 넣어준 뒤, Queue에 차례대로 넣어가며 Queue에 존재하는 보석의 종류수가 Set의 크기와 동일하면 모든 보석을 포함하는 경우이다.

 

Queue에 보석을 하나씩 넣어가며 Map에 현재 보석의 개수를 추가해주었다. 추가하면서 만약 Queue의 제일 앞의 보석의 개수가 1보다 크다면 그 보석이 없더라도 이미 모든 보석을 가지고 있기 때문에 반복해서 제거해주었다.

 

모든 보석을 포함하고 있으면서 보석을 누적한 길이가 기존 길이보다 작다면 답을 갱신해주었다.

 

💻 코드

import java.util.*;

class Solution {
    public int[] solution(String[] gems) {
        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;
            }
        }

        return new int[]{start, start + len};
    }

}