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

링크 : https://programmers.co.kr/learn/courses/30/lessons/67258?language=java# 

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

 

참고 링크 : https://hidelookit.tistory.com/174

[프로그래머스] (2020 카카오 인턴십) 보석 쇼핑 (Java)

 

 

- 풀이

 - 투포인터 사용 문제

 - map으로 들어오는 보석(String) 숫자를 기록하고 모든 숫자가 1이상일 때 조건을 충족하기 때문에 해당 시점의 index start, end 를 각각 기록한다.

 - 하지만 첫 while 문에서는 right로만 진행하고 있어서 앞에 충분히 지울 수 있지만 중복되어 (숫자가 2 이상인) 지울 수 있는 element 가 있는 지 확인하고 지울 수 있다면 left를 ++ 한다 (left, right 기록, 최소값이 조건이기에 최소값 기록해준다.)

 - index end 가 gems length에 도달했을 때 체크를 끝낸다.

 

 

import java.util.*;
class Solution {
    public int[] solution(String[] gems) {
        int[] answer = new int[2];
        
        Set<String> set = new HashSet<String>();
        for(String gem: gems) {
            set.add(gem);
        }
        
        int left = 0;
        int right = 0;
        
        int start = 0;
        int end = 0;
        
        int distance = Integer.MAX_VALUE;
        
        HashMap<String, Integer> map = new HashMap();
        
        while(right < gems.length) {
            
            if (map.size() < set.size()) {
                map.put(gems[right], map.getOrDefault(gems[right], 0) + 1);
                right++;
            }
            
            while(map.size() == set.size()) {
                map.put(gems[left], map.get(gems[left])-1);
                if(map.get(gems[left]) == 0) {
                    map.remove(gems[left]);
                }
                left++;
                
                if(right-left < distance) {
                    distance = right-left;
                    start = left;
                    end = right;
                }
                
            }
        }
        
        answer[0] = start;
        answer[1] = end;
        
        return answer;
    }
}