[프로그래머스] [카카오 인턴] 보석 쇼핑 - 자바(JAVA)

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

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

 

문제 해석

어피치는 쇼핑을 하면 매장 진열대의 특정 범위의 물건을 모두 구매합니다.

어피치는 진열된 모든 종류의 보석을 적어도 1개 이상 포함하는 가장 짧은 구간을 찾아서 구매하고 싶었습니다.

 

문제 풀이 전 설계

gems 배열의 크기는 10만입니다.

 

투포인터 문제 같습니다.

포인터 2개를 0부터 시작하여 오른쪽포인트를 오른쪽으로 이동시킵니다.

이때 오른쪽포인터를 이동시킵니다. (모든 보석을 1개이상 포함하는 구간까지)

이후에 왼쪽포인터를 이동시킵니다. (모든 보석을 1개이상 포함하는 구간까지)

하나의 최소구간이 될 수 있는 후보가 만들어졌습니다.

 

이후에 왼쪽포인터를 이동시키고 다시 오른쪽포인터를 이동시키면서 최소구간을 탐색하여 갱신합니다.

 

코드

import java.util.*;

public class Solution_카카오인턴_보석쇼핑2 {
    public static void main(String[] args) {
        String[] gems = {"DIA", "RUBY", "RUBY", "DIA", "DIA", "EMERALD", "SAPPHIRE", "DIA"};
        Set<String> uniqueGems = new HashSet<>();
        for(String curString : gems){
            uniqueGems.add(curString);
        }
        Map<String, Integer> curGemsCount = new HashMap<>();
        Queue<String> q = new LinkedList<>();
        int leftPoint = 0;
        int size = Integer.MAX_VALUE;
        int result = 0;
        // i = rightPoint 역할
        for(int i=0; i< gems.length; i++){
            //배열을 돌면서 hashMap 에 없다면 값을 추가하고 그렇지 않다면 개수를 추가합니다.
            if(!curGemsCount.containsKey(gems[i])){
                curGemsCount.put(gems[i],1);
            } else{
                curGemsCount.put(gems[i],curGemsCount.get(gems[i])+1);
            }
            //Queue에 보석담기
            q.add(gems[i]);

            //만약 queue의 첫번째 보석의 개수가 1개를 초과한다면 leftPoint 당겨옵니다.
            while(true){
                String temp = q.peek();
                if(curGemsCount.get(temp) > 1){
                    curGemsCount.put(temp, curGemsCount.get(temp)-1);
                    q.poll();
                    leftPoint++;
                } else{
                    break;
                }
            }

            //case 1 : 보석이 모두 들어있는 경우를 확인
            //case 2 : 구간의 길이가 더 작은경우 갱신
            if(curGemsCount.size() == uniqueGems.size() && size > q.size()){
                size = q.size();
                result = leftPoint;
            }
        }
        System.out.println(result+1 + " " + (result + size));
    }
}