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

문제

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

프로그래머스

풀이

풀이 원리는 투포인터를 이용한 윈도우 슬라이더를 유지하면서 풀었다.

리트코드에서 풀었던 최대 빈도수와 원리는 같다. 

 

https://0713k.tistory.com/11

[java/python3]leetcode 1838. Frequency of the Most Frequent Element

알고리즘은 다음과 같다. 

1. set을 사용하여 보석 종류의 개수를 센다. 
2. gem 배열을 탐색하면서, 해시맵으로 보석 종류별 개수를 매핑한다. 
3. 보석 종류가 보석 최대 개수 k개에 다다랐을떄, left 포인터를 무빙하면서 답을 갱신한다.
4. right가 끝에 다다르면 반복문을 종료한다.

 

---

참고

해시맵에서 key 가 없을때,  java.util.HashMap.merge 메소드를 사용하여 (key, value)를 삽입하였는데,

 

map.put(map.getOrDefault(key,0)+1);

getOrDefault 랑 비교해보니 getOrDefault 가 수행시간이 두배더 빠른것을 확인할 수 있었다. 

 

궁금한건 못참지.  getOrDefault 쓰세요~

코드

import java.util.*;

class Solution {
    public int[] solution(String[] gems) {
        int[] answer = new int[] {};
        HashSet<String> gemCnt = new HashSet<>(Arrays.asList(gems));//보석 종류의 개수
        HashMap<String, Integer> map = new HashMap<>();
        
        int left =0 ; 
        int right = 0;
        int min = Integer.MAX_VALUE;
        
        while(right < gems.length){
            map.merge(gems[right], 1, Integer::sum);
            int size = map.size();

            while(size == gemCnt.size()){
                if(min >right - left +1 ){
                    
                    answer = new int[]{left+1,right+1};
                    min = right - left + 1;
                }
                map.merge(gems[left],-1,Integer::sum);
                if(map.get(gems[left])==0){
                    map.remove(gems[left]);
                    size--;
                }
                left++;
            }            
            right++;
        }
        
        return answer;
    }
}