[JAVA] 보석 쇼핑

문제

https://programmers.co.kr/learn/courses/30/lessons/67258?language=java 

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

내 풀이

import java.util.*;

class Solution {

    public int[] solution(String... gems) {
        int[] answer = new int[2];
        // 리스트 내 모든 보석 종류를 빠른속도로 카운팅할 수 있다.
        Set<String> allKinds = new HashSet<>();
        Collections.addAll(allKinds, gems);


        int last = 0;
        Map<String, Integer> slideCounter = new HashMap<>();

        // 초기 정답 길이를 무한으로 세팅한다 (거의 무한)
        int dist = (int) 10e6;
        for (int i = 0; i < gems.length; i++) {
            // 슬라이드 내 보석의 종류가  전체 보석의 종류 수와 같을때 까지 오른쪽으로 크기를 키운다
            while (last < gems.length && slideCounter.size() < allKinds.size()) {
                slideCounter.put(gems[last], slideCounter.getOrDefault(gems[last], 0) + 1);
                last++;
            }
            // 만약 전체보석 종류수만큼 슬라이드가 보석종류를 가진다면
            if (slideCounter.size() == allKinds.size()) {
                // 그 슬라이드의 길이가 정답에 해당하는 이전 슬라이드보다 짧으면
                if (last - i < dist) {
                    // 정답과 길이를 업데이트 해준다
                    answer[0] = i + 1;
                    answer[1] = last;
                    dist = last - i;
                }
            }
            // start 인덱스를 오른쪽으로 밀기 전에, start 인덱스의 보석을 빼준다
            if (slideCounter.get(gems[i]) == 1) {
                slideCounter.remove(gems[i]);
            } else {
                slideCounter.put(gems[i], slideCounter.getOrDefault(gems[i], 0) - 1);
            }

        }
        // 모든 슬라이드를 점검해 가장 짧은데 모든 보석종류를 가지는 부분 리스트를 리턴한다
        return answer;
    }
}

알게 된 것

투 포인터를 통해 조건에 만족하는 배열의 최소 리스트들을 찾거나 갯수를 셀 수가 있다.

Prefix Sum 과 함께, 배열의 어떤 조건에 맞는 경우를 찾을 때 유용하다.

 

피드백

 

1. 쉬운데 나 스스로의 자만으로 어려워졌다. 무조건 시작점을 0으로 고정시켜놓고 했다. 하지만 모든 인덱스가 시작점이 되어야 가능한 모든 윈도우를 검사할 수 있는 것이었다. 나 스스로 Greedy 하게 풀려고 하지말아야겠다.

 

2. Collections.addAll(Collection, T... elements); 를 사용하면 배열내 모든 원소를 Collection 에 add 가능하다. List,Set에 유용할듯