프로그래머스 - (Java) 보석쇼핑

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

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

1. 유형

해쉬맵, 큐

 

2. 로직

1. 총 보석의 종류를 파악
2. 해쉬맵에서 {보석이름, 개수}형태로 딕셔너리 생성
3. 투포인터를 사용해서 모든 종류의 보석을 포함하고 있는 범위를 구함

gems가 아래처럼 주어졌다고 할때, 

["DIA", "RUBY", "RUBY", "DIA", "DIA", "EMERALD", "SAPPHIRE", "DIA"]

 

위의 그림처럼 시뮬레이션을 하면 start=3, end=4가 된다.

위의 방법처럼 start, end 변수를 갱신하면 된다.

 

3. 코드

import java.util.*;
class Solution {
    public int[] solution(String[] gems) {
	        HashMap<String, Integer> map = new HashMap<>();
	        Queue<String> q = new LinkedList<>();
	        Set<String> set = new HashSet<>();
	        set.addAll(Arrays.asList(gems));
	        int len = set.size();
	        int answer[]=new int[2];
	        int start = 1, end=0, tempsize=Integer.MAX_VALUE;
	        
	        for(String gem: gems){
	            map.put(gem, map.getOrDefault(gem, 0)+1);
	            q.add(gem);
	            end++;
	            while(map.get(q.peek())>1){
	                map.put(q.peek(), map.get(q.peek())-1);
	                start++;
	                q.poll();
	            }
	            if(len == map.size() && tempsize > end-start){
	                tempsize = end - start;
	                answer[0]=start;
	                answer[1]=end;
	            }
	        }
	        return answer;
	    }
}