[lv3] 보석 쇼핑

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

 

1. 전처리

문자로 비교하면 비효율적이다.

 

int gTotal = 존재하는 보석 가짓수

int[] gemArr = 보석 이름(문자열) 대신 int key로 비교할 배열

 

2. 투포인터 + 슬라이딩 윈도우

int total = 현재 윈도우에 포함되는 보석 가짓수

 

total < gTotal  : 정답 조건을 만족하지 않으므로 ed++;

total == gTotal : 정답과 비교 및 st++;

(현재 윈도우에 st를 높혀도 정답인 경우가 존재할 수 있음)

 

ed가 끝에 닿은 경우

total == gTotal : 정답이 될 수 있는 경우의 수가 남았으므로 st++;

total < gTotal : st++을 계속 해도 total이 늘어날 순 없으므로 모두 해가 아님. 탐색 종료

 

3. if(st > ed) ed = st ?

결론은 안써도 정답이긴 하다. 고려한 이유는 다음과 같다.

 

배열이 [A,A,A]인 경우, gTotal = 1이다.

 

초기 st = 0, ed = 0의 탐색 (0번째 A)에서

total 역시 1이므로 total  == gTotal을 만족한다.

그렇기에, 답을 갱신하고  st++;하여 st = 1, ed = 0 (st > ed)꼴이 나오게 된다.

 

이는 투 포인터에서 나오면 안되는 상황이지만, 문제에서 gTotal = 1인 경우에만 발생 가능하다.

 

 gTotal = 1인 경우, 첫 번째 탐색인 st = 0, ed = 0에서 답 후보로 기록되고,

이는 st가 가장 왼쪽인 경우기에 나머지 탐색은 정상적이던 비정상적이던 답을 갱신하지 않는다.

 

따라서 에러만 안나면 정답이지만 예상치 못한 상황을 낼 수 있기에 고려했다.

 

import java.util.*;

class Solution {
    public int[] solution(String[] gems) {

        int minSize = Integer.MAX_VALUE;
        int minLeft = -1;
        int minRight = -1;

        int gl = gems.length;
        int gTotal = 0;
        int[] gemArr = new int[gl];

        Map<String, Integer> map = new HashMap<>();

        for(int i=0; i<gl; i++) {
            String gem = gems[i];

            if(!map.containsKey(gem)) {
                map.put(gem, gTotal++);
            }

            gemArr[i] = map.get(gem);
        }

        int st = 0;
        int ed = st;
        int total = 0;

        int[] nowG = new int[gTotal];

        nowG[gemArr[0]]++;
        total++;

        while(true) {

            if(total == gTotal) {
                int size = ed - st + 1;

                if(size < minSize) {
                    minSize = size;
                    minLeft = st;
                    minRight = ed;
                }

                // 만약 가장 짧은 구간이 여러 개라면 시작 진열대 번호가 가장 작은 구간을 return
                else if(size == minSize && st < minLeft) {
                    minLeft = st;
                    minRight = ed;
                }

                int firstG = gemArr[st];

                if(nowG[firstG] == 1) {
                    total--;
                }

                nowG[firstG]--;
                st++;

                if(st > ed) {
                    ed = st;
                }

            }
            else {

                // ed가 끝에 닿은 상태인데도 total == gTotal를 만족하지 않으면 종료
                if(ed == gl - 1) break;

                ed++;

                int lastG = gemArr[ed];

                if(nowG[lastG] == 0) {
                    total++;
                }

                nowG[lastG]++;
            }
        }

        return new int[]{minLeft+1, minRight+1};
    }
}