프로그래머스: 보석 쇼핑 [JAVA]

문제 링크

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

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

풀이

전체적인 풀이 과정은 다음과 같다.

1. 반복문을 통해 주어진 gems 속 보석의 종류 가짓수를 파악
2. 끝구간을 0부터 끝까지 반복문으로 하나씩 더해가며 0부터 해당 위치까지의 보석 가짓수가 전체 종류와 같은지 확인
3. 보석 가짓수와 전체 종류가 같다면 시작 인덱스를 어디까지 줄일 수 있는 지를 체크
4. 최종적으로 주어진 시작과 끝 인덱스를 통해 길이를 계산하여 최소 길이면 답을 최신화

 문제 자체에서 효율성 테스트 부분을 언급하기도 하고, 문제 속 gems의 길이가 최대 100,000이 되기 때문에 만약 특정위치부터 모든 보석 종류를 구매할 수 있는 끝 구간을 찾아나서는 방법으로 알고리즘을 작성하면 시간 초과가 날 수 있다.

 그러기 때문에 이전 정보를 최대한 활용하면서 최소 구간을 찾아야 하는데, 이런 경우 사용한 방법이 끝 구간을 고정하는 방법이다. 첫 구간을 앞으로 더하며 해당 부분을 기준으로 잡는 경우, 이전 위치 보석들의 정보가 쓸모가 없는 반면, 끝 구간을 하나씩 더하며 해당 부분을 기준으로 잡는 것은 이전 위치 보석들의 정보가 구간 내부에 포함되기 때문에 그대로 활용할 수 있다.

 그렇게 끝 구간을 정하고 나면 전체적인 최소 구간을 구하기 위해 시작 부분인 인덱스 0부터 이제 모든 보석의 종류가 유지되고 있는 지점까지 시작 부분을 줄여 나간다. 그렇게 최종적으로 나온 시작과 끝 지점을 통해 해당 길이가 최소인지를 확인하고 답을 최신화한다. 물론 이때도 시작 부분 인덱스가 이전 구간에서의 시작 부분 인덱스보다 더 작을 수가 없기 때문에, 시작 부분에 대한 인덱스도 매번 반복문마다 그대로 활용할 수 있다.

class Solution {
    int startIndex = 0, endIndex, answerLength = 999999, gemKinds;
    HashMap<String, Integer> map = new HashMap<>();
    HashSet<String> set = new HashSet<>();

    public int[] solution(String[] gems) {
        int[] answer = new int[2];

        for (int i = 0; i < gems.length; i++)//전체 보석 종류를 파악
            set.add(gems[i]);

        gemKinds = set.size();//전체 보석 가짓수 저장

        for (int i = 0; i < gems.length; i++) {//하나씩 지나가며
            String gem = gems[i];

            if(map.containsKey(gem))//개수 파악용 Hashset에 종류의 개수 추가
                map.put(gem, map.get(gem) + 1);
            else
                map.put(gem, 1);

            if (map.size() == gemKinds) {//gems의 0부터 현재까지 모든 보석 종류가 들어가 있다면
                endIndex = i;
                cutTail(gems);//시작부분의 0을 최대한 줄여나감

                if (endIndex - startIndex < answerLength) {//길이 비교 후 저장
                    answerLength = endIndex - startIndex;
                    answer[1] = endIndex + 1;
                    answer[0] = startIndex + 1;
                }
            }
        }

        return answer;
    }

    private void cutTail(String[] gems) {//0부터 주어진 인덱스까지의 구간에서 시작부분을 잘라나감
        while (true) {//구간 속 보석 가짓수가 전체 보석 가짓수와 동일할 때까지 반복
            String gem = gems[startIndex];
            int count = map.get(gem);

            if (count > 1) {
                map.put(gem, count - 1);
                ++startIndex;
            }
            else
                break;
        }
    }
}

결과