[2020 카카오 인턴십] 보석 쇼핑

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

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

 

 

## 접근

---

• 직관적으로 생각해야 답이 있다. 처음에는, 모든 범위에서 양쪽 범위를 줄여가며 탐색하려고 했다. 하지만 이 경우에는, N * N의 시간복잡도를 가졌다. 정확성 테스트는 통과했지만, 효율성 테스트는 통과하지 못했다.
  
  
  
  
• 따라서, N * logN이나 N의 시간복잡도를 가지도록 코드를 설계해야 했다.
  
  
  
  
• 보석의 개수를 중복을 제거할 수 있는 자료 구조를 통해서 구한다. 순차적으로, 보석들을 읽어가면서, 보석의 개수가 완성이 됐을 때 제일 앞의 보석을 제거하면서 최소 범위를 찾는다. 그러던 도중 모든 보석들을 포함하지 못하게 됐을 때 뒤의 보석을 하나씩 추가해준다. 이 과정을 반복하면 정답을 구할 수 있다.

 

 

 

## 해설코드

---

import java.util.*;
 
class Solution {
    HashMap<String, Integer> hm = new HashMap<>();
        
    public int[] solution(String[] gems) {
        int[] answer = new int[2];
        
        for(int i = 0; i < gems.length; i++){
            hm.put(gems[i], hm.getOrDefault(gems[i], 0) + 1);
        }
        
        int total = hm.size();
        hm.clear();
        
        int start = 0; 
        int end = 0;
        
        int s = 0;
        int e = gems.length - 1;
        
        while(true){
            hm.put(gems[end], hm.getOrDefault(gems[end], 0) + 1);
            
            while(hm.size() == total){
                if(end - start + 1 < e - s + 1){
                    e = end;
                    s = start;
                }
                
                hm.put(gems[start], hm.get(gems[start]) - 1);
                if(hm.get(gems[start]) == 0)
                    hm.remove(gems[start]);
                
                start += 1;
                if(start >= end)
                    break;
            }
                
            end += 1;
            if(end == gems.length)
                break;
        }
        
        s = s + 1;
        e = e + 1;
        
        answer[0] = s;
        answer[1] = e;
        
        return answer;
    }
}