프로그래머스 LV3 - 보석쇼핑

처음 문제를 접했을 땐

단순히 모든 보석을 포함하는 시점에서,

각 보석들의 마지막 등장 인덱스 중 가장 작은 인덱스를 시작 지점으로 잡았다.

하지만 모든 보석을 포함하는 시점에서의 최소 인덱스를 찾을 뿐, 

전체의 가장 짧은 구간을 찾을 순 없었다.

그래서 슬라이딩 윈도우를 사용했다.

 

import java.util.*;

/* 
    https://school.programmers.co.kr/learn/courses/30/lessons/67258
    gems	result
    ["DIA", "RUBY", "RUBY", "DIA", "DIA", "EMERALD", "SAPPHIRE", "DIA"]	[3, 7]
    ["AA", "AB", "AC", "AA", "AC"]	[1, 3]
    ["XYZ", "XYZ", "XYZ"]	[1, 1]
    ["ZZZ", "YYY", "NNNN", "YYY", "BBB"]	[1, 5]
 */
public class 보석_쇼핑 {

    public void solution() {

        final String[] gems = { "DIA", "RUBY", "RUBY", "DIA", "DIA", "EMERALD", "SAPPHIRE", "DIA" };

        long gemCount = Arrays.stream(gems).distinct().count();

        // 현재 구간 내의 보석들을 포함.
        Map<String, Integer> gemCountMap = new HashMap<>();
        // 초기화
        int left = 0, right = 0, minLength = Integer.MAX_VALUE;
        int start = 0, end = 0;

        while (right < gems.length) {
            gemCountMap.put(gems[right], gemCountMap.getOrDefault(gems[right], 0) + 1);
            right++;

            // 모든 보석이 포함되어 있을 경우, start를 한칸씩 이동하며 minLength를 줄여나간다.
            while (gemCountMap.size() == gemCount) {
                if (right - left < minLength) { // 현재 구간이 가장 짧은 경우
                    minLength = right - left; // 구간 길이 갱신
                    start = left + 1; // 구간 시작지점 갱신
                    end = right; // 구간 종료지점 갱신
                }

                // 계산이 끝난 left의 값을 정리.
                gemCountMap.put(gems[left], gemCountMap.get(gems[left]) - 1);
                if (gemCountMap.get(gems[left]) == 0) {
                    gemCountMap.remove(gems[left]);
                }

                // left 한칸 이동
                left++;
            }
        }

        int[] answer = { start, end };

        System.out.println(Arrays.toString(answer));

    }

}

 

right로 한칸씩 구간을 넓혀가며 보석이 모두 포함된 순간,

left를 한칸씩 이동하며 가장 짧은 구간을 좁혀간다.

가장 짧은 구간인 경우,  구간의 length와 start, end를 갱신한다.

 

반복이 모두 끝난 후 start와 end로 배열을 만들어 반환한다.

 

정확성과 효율성을 모두 검사하고 gems의 범위가 1부터 10만인 문제라,

사실상 슬라이딩 윈도우밖엔 답이없는 문제였다. 굿굿~

 

 

250212

다시 생각해보니, 지금 수준에서 LV3문제를 푼게 거의 기적에 가깝다.

풀고나서 LV3인걸 보고 쿨한척 했지만 우쭐했다.

책에서 문제를 줘서 어찌어찌 풀었지만은..  시간은 우장창 걸렸다.

뭐.. 풀만 하니까 줬었겠지? 싶기도 하다.