[프로그래머스] 보석 쇼핑 / 2020 카카오 인턴십 - JAVA

🖇️ 문제 링크

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

개발자 출신으로 세계 최고의 갑부가 된 어피치는 스트레스를 받을 때면 이를 풀기 위해 오프라인 매장에 쇼핑을 하러 가곤 합니다. 어피치는 쇼핑을 할 때면 매장 진열대의 특정 범위의 물건들을 모두 싹쓸이 구매하는 습관이 있습니다. 어느 날 스트레스를 풀기 위해 보석 매장에 쇼핑을 하러 간 어피치는 이전처럼 진열대의 특정 범위의 보석을 모두 구매하되 특별히 아래 목적을 달성하고 싶었습니다.

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

 

---

📝 문제 분석

보석 종류의 개수를 구하고 시작합니다. (스트림 사용)

해시맵과 큐에 보석을 하나씩 넣습니다. 맵에 보석 전체 종류가 다 들어가게 되면, 모든 보석이 다 있어야 한다는 조건은 만족하는 상태로 처음 넣었던 보석부터 제거해 나갑니다.

조건을 만족하는 최소 범위이기 때문에, 큐에 남아있는 보석이 최소가 되는 범위를 리턴합니다.

 

 

---

⌨️ 코드

import java.util.*;
class Solution {
    public int[] solution(String[] gems) {
        HashMap<String, Integer> hm = new HashMap<>();
       	int total = (int)Arrays.stream(gems)
            .distinct()
            .count();
        
        Queue<String> q = new LinkedList<>();
        int idx = 1, s = 0, ret = Integer.MAX_VALUE;
        for(String gem : gems) {
            hm.put(gem, hm.getOrDefault(gem, 0) + 1);
            q.add(gem);
            
            while(hm.get(q.peek()) > 1) {
                String str = q.poll();
                hm.put(str, hm.get(str) - 1);
                idx++;
            }
            
            if(hm.size() == total && ret > q.size()) {
                s = idx;
                ret = q.size();
            }
        }
        return new int[]{s, s + ret - 1};
    }
}

 

 

 

 

Uploaded by Notion2Tistory v1.1.0