[JAVA] 프로그래머스 (Lv.3) 보석 쇼핑

링크

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

---

입력 예제

["DIA", "RUBY", "RUBY", "DIA", "DIA", "EMERALD", "SAPPHIRE", "DIA"]

---

출력 예제

[3, 7]

---

풀이

문제의 조건은 진열된 모든 종류의 보석을 적어도 1개 이상 포함하는 가장 짧은 구간을 찾아서 구매인데 결국 모든 보석 종류를 포함하는 구간 중 가장 짧은 구간을 찾아야 한다.

특정 구간을 찾아야 하므로 투포인터로 조건을 만족하는 구간을 찾는다. 예제에 대하여 [0, 0]부터 시작한다면 우선 DIA를 맵에 추가한다.

• [0, 0]: [DIA: 1, RUBY: 0, EMERALD: 0, DIA: 0]

그리고 아직 보석의 종류가 만족되지 않았으니 구간을 확장한다.

• [0, 1]: [DIA: 1, RUBY: 1, EMERALD: 0, DIA: 0]

이런 식으로 모든 보석을 포함할 때 까지 반복하면 다음과 같은 상태가 된다.

• [0, 6]: [DIA: 3, RUBY: 2, EMERALD: 1, DIA: 1]

이제 구간을 축소해가며 최소 구간이 될 때를 찾아야한다.

• [1, 6]: [DIA: 2, RUBY: 2, EMERALD: 1, DIA: 1]
• [2, 6]: [DIA: 2, RUBY: 1, EMERALD: 1, DIA: 1]
• [3, 6]: [DIA: 2, RUBY: 0, EMERALD: 1, DIA: 1]

[3, 6]에서 RUBY가 0개가 되므로 조건을 만족하는 최단 구간은 [2, 6]이 되며 문제는 1-based 배열이므로 답은 [3, 7]이 된다.

전체 코드

import java.util.Arrays;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Set;

/*
프로그래머스 / 보석 쇼핑 / Level3
https://school.programmers.co.kr/learn/courses/30/lessons/67258
 */
class Solution {

    public int[] solution(String[] gems) {
        Set<String> gemTypes = new HashSet<>(Arrays.asList(gems));
        int typeCount = gemTypes.size();  //보석의 종류

        Map<String, Integer> gemCount = new HashMap<>();
        int start = 0, end = 0;
        int minLength = Integer.MAX_VALUE;
        int[] result = new int[2];

        while (end < gems.length) {
            //현재 구간에 보석을 추가
            String lastGem = gems[end];
            gemCount.put(lastGem, gemCount.getOrDefault(lastGem, 0) + 1);

            while (gemCount.size() == typeCount) {  //모든 종류의 보석을 포함할 경우
                int length = end - start;
                if (length < minLength) {  //최소 구간 길이 갱신
                    minLength = length;
                    result[0] = start + 1;
                    result[1] = end + 1;
                }

                //구간 시작점 보석 제거
                String firstGem = gems[start];
                gemCount.put(firstGem, gemCount.get(firstGem) - 1);
                if (gemCount.get(firstGem) == 0) {
                    gemCount.remove(firstGem);
                }

                start++;  //구간 축소
            }

            end++;  //구간 확장
        }

        return result;
    }
}