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

문제 링크: 프로그래머스 Lv. 3 보석 쇼핑

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

 

투 포인터를 통해 해결할 수 있는 문제이다.

left와 right를 움직여주면서 [left, right] 구간 내에 모든 보석이 1개 이상 포함된다면, 이 때 시작 진열대 번호와 끝 진열대 번호를 갱신한다.

이러한 과정에서 left와 right는 다음과 같이 움직인다.
구간 내에 모든 보석이 포함되어 있다면? 이 때에는 크기를 줄여본다. 즉 left를 1 증가시킨다.
구간 내에 모든 보석이 포함되어 있지 않다면? 이 때에는 더 많은 보석을 보아야 한다. 즉 right를 1 증가시킨다.

 

한편 구간 내에 모든 보석이 포함되어 있는지의 여부에 대해서는 어떻게 알 수 있을까? gems 배열의 크기는 1 이상 100,000 이하라고 했으므로 O(n)으로 해결되어야 한다. 다시말해 left나 right를 옮길 때마다 구간을 순회하면서 확인하는 O(n^2)의 방법은 이용하지 못한다.
이를 위해 각 보석의 개수인 int[] count와, 포함된 보석의 종류 int included를 이용할 수 있다. 각 보석의 크기를 count에 보관하되, left를 움직여서 특정 보석이 제외될 때(count[i]의 값이 1에서 0이 될 때) 또는 right를 움직여서 특정 보석이 추가될 때(count[i]의 값이 0에서 1이 될 때)에는, included를 각각 감소시키거나 증가시키는 것이다.

map을 이용하여 key에는 보석, value에는 보석의 개수를 두고 map의 크기를 확인함으로써 included를 대체할 수도 있으나, 조금 더 C 스타일에 가까운 전자의 방법이 범용적일 것이다.

 

import java.util.*;

class Solution {
    static int numGemType = 0;
    static int numGemShow = 0;
    static Map<String, Integer> map = new HashMap<>();
    static int answerLen = Integer.MAX_VALUE;
    static int answer1 = -1;
    static int answer2 = -1;

    public int[] solution(String[] gems) {
        init(gems);

        int left = 0;
        int right = 0;
    
        // while문 진입 시 이미 [left, right] 구간에 대한 탐색이 완료되었다고 가정하므로
        // while문 진입 이전에 초기값 세팅이 필요하다.
        // 또는 left = -1, right = -1로 설정하는 방법이 있다.

        int[] count = new int[numGemType];
        int included = 1;
        count[map.get(gems[0])]++;

        while (true) {
            if (included == numGemType) {
                if (right - left + 1 < answerLen) {
                    answerLen = right - left + 1;
                    answer1 = left;
                    answer2 = right;
                }

                count[map.get(gems[left])]--;
                if (count[map.get(gems[left])] < 1) included--;
                left++;
            } else {
                right++; if (right >= numGemShow) break;
                if (count[map.get(gems[right])] < 1) included++;
                count[map.get(gems[right])]++;
            }

        }

        return new int[]{answer1+1, answer2+1};
    }

    static void init(String[] gems) {
        numGemShow = gems.length;

        int idx = 0;
        for (String g : gems) {
            if (!map.containsKey(g)) {
                map.put(g, idx);
                idx++;
            }
        }

        numGemType = map.size();
    }
}