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

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

프로그래머스

 

접근 방법

1. gems 배열의 크기는 10만 이하이므로 O(n^2)은 안된다.
2. 조건에 맞는 구간을 찾는 문제이므로 투포인터 생각
3. 구간내에 모든 보석 종류가 있는지 확인해야하므로 set에 보석을 담아 보석 종류 개수 저장
4. 투포인터 구현
   1. right 포인터를 움직이며 구간을 늘린다 => map에 보석종류별로 몇개 나왔는지 저장
   2. left 포인터를 움직이는 조건: 포인터가 있는 보석이 1개 초과인 경우 움직이며 구간을 좁힌다
   3. 길이 저장 조건: map 사이즈 == 보석 전체 종류

코드

import java.util.*;
class Solution {
    public int[] solution(String[] gems) {
        Set<String> set = new HashSet<>();
        for(String g: gems)set.add(g);
        int totCate = set.size();
        
        int l = 0;
        int len = Integer.MAX_VALUE;
        Map<String, Integer> map = new HashMap<>();
        int[] ans = new int[2];
        
        for(int r = 0 ; r < gems.length ; r++){
            map.put(gems[r], map.getOrDefault(gems[r], 0) + 1);
            
            while(map.get(gems[l]) > 1){
                map.put(gems[l], map.get(gems[l])-1);
                l++;
            }
            
            if(map.size() == totCate && len > r-l){
                len = r-l;
                ans[0] = l+1;
                ans[1] = r+1;
            }
        }
        
        return ans;
    }
}