프로그래머스_카카오인턴십_보석쇼핑_자바

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

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

모든 보석들을 한번씩 포함하는 배열의 시작인덱스와 끝인덱스를 구하는 문제이다.

가능 한 모든 경우를 for 문을 돌면서 구한다면 쉽게 구할수있지만 효율성 검사를 통과하지 못한다.

핵심로직 ! 

 

1. 배열의 보석들을 닮을 큐를 만들어준다.

2. 전체 보석이 몇개인지 저장하기위해서 hashSet 를 하나 만들어준다.

3. hashMap 을 사용하여 큐에 보석들을 담을때마다 hashMap에 개수를 저장해준다.

4. 만약 hashMap 의 사이즈와  hashSet 의 사이즈가 같다는 것은 모든 보석을을 한번씩 포함하는 것을 의미함으로

   시작지점과 그때의 큐 사이즈를 저장해준다.

 

다음은 전체 코드이다. 

import java.util.HashMap;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.Queue;

class Solution {
      static Queue<String> q = new LinkedList<String>();
      static HashSet<String> hs = new HashSet<String>(); 
      static HashMap<String, Integer> hm = new HashMap<String, Integer>();
      static int startPoint = 0;
      static int length = Integer.MAX_VALUE;
     public static int[] solution(String[] gems) {
        int[] answer;  
        for(String g : gems) {
        	hs.add(g);
        }
        int start = 0;
        for(int i = 0; i < gems.length; i++) {
        	
        	// 배열을 돌면서 hashMap 에 없다면 값을 추가해고 
            // 있다면 개수를 하나 추가해준다.
        	if(!hm.containsKey(gems[i])) hm.put(gems[i], 1);
        	else hm.put(gems[i], hm.get(gems[i]) + 1);
        	
        	// 큐에 보석을담아 준다.
        	q.add(gems[i]);
        	
        	// 큐에 첫번째 보석의 개수가 1개 를 초과한다면 startPoint 를갱신해주고 q에서 빼준다.
        	while(true) {
        		String temp = q.peek();
        		if(hm.get(temp) > 1) {
        			hm.put(temp, hm.get(temp) - 1);
        			q.poll();
        			startPoint++;
        		}
        		else {
        			break;
        		}
        	}
        	// 만약 현재 큐에있는 보석이 모든 보석을 포함한하고(hm 의 크기와 hs 에 크기가 같다면)
        	// 새로구한 구간이 현재 구간의 길이보다 작다면 최종 시작포인트 값인 start 값을 갱신해준다.
        	if(hm.size() == hs.size() && length > q.size()) {
        		length = q.size();
        		start = startPoint;
        	}
        }
        return new int[]{start + 1, start + length};  
    }
}