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

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

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

카카오 2019 인턴십 기출 문제인 보석 쇼핑입니다.

해당 코딩테스트를 직접 응시했었는데 투 포인터가 아닌 우선순위큐로 문제를 풀었던 경험이 있는데 시간복잡도로는 안되지만 통과했었습니다. 해당 테스트 당시에는 테스트케이스가 약했나?싶었던 기억이 있는 문제입니다.

 

제가 투포인터에 약한 모습을 보이므로 이 문제를 풀었습니다.

 

풀이 방법은 의외로 간단합니다.

두개의 포인터 l과 r을 선언하고 0번 idx를 가리키도록 정의합니다.

이후 반복문을 돌면서 모든 보석을 포함하고 있지 않다면 r포인터를 하나씩 늘리고 해당 보석을 포함하면서 확인합니다.

만약 모든 보석을 포함한다면 l포인터를 하나씩 늘리고 원래 l idx에 있던 보석을 제외합니다. 그리고 제외하고도 모든 보석을 포함할 수 있는지 확인하는 방식입니다.

import java.util.*;

class Solution {
    static int mn = (int)1e9,N,gemCnt,answer[] = new int[2];
    public int[] solution(String[] gems) {
        N = gems.length;
        HashSet<String> gemSet = new HashSet<String>();
        for(int i=0;i<N;i++){
            String gem_name = gems[i];
            if(!gemSet.contains(gem_name)) gemSet.add(gem_name);
        }
        gemCnt = gemSet.size();
        int l= 0, r= 0, cnt= 0;
        HashMap<String, Integer> gemCheck = new HashMap<String, Integer>();
        gemCheck.put(gems[0],1);
        cnt++;
        while(l<=r && r<N){
            if(cnt == gemCnt){
                if(mn>r-l+1){
                    mn = r - l + 1;
                    answer[0] = l+1;
                    answer[1] = r+1;
                }
                int targetGemCnt = gemCheck.containsKey(gems[l]) ? gemCheck.get(gems[l])-1:0;
                gemCheck.put(gems[l],targetGemCnt);
                if(gemCheck.get(gems[l])==0) cnt--;
                l++;
            }
            else{
                r++;
                if(r>=N) continue;
                int targetGemCnt = gemCheck.containsKey(gems[r]) ? gemCheck.get(gems[r])+1:1;
                gemCheck.put(gems[r], targetGemCnt);
                if(targetGemCnt == 1) cnt++;
                gemSet.add(gems[r]);
            }
        }
        return answer;
    }
}