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

문제

진열된 보석들 중 모든 종류의 보석을 적어도 하나 이상 포함하는 가장 짧은 구간을 찾아야 한다.

조건은 다음과 같다:

• 보석의 진열 순서가 담긴 문자열 배열 gems가 주어진다.
• 진열된 보석들을 연속적으로 선택한 구간 중, 모든 보석 종류를 한 번 이상 포함하는 가장 짧은 구간의 시작과 끝 인덱스를 반환한다.
• 정답이 여러 개인 경우, 시작 인덱스가 가장 작은 구간을 반환한다.

---

풀이 방법

풀이 시간 : 1시간

풀이 방법 : 투포인터 + 해시맵 (슬라이딩 윈도우)

 

반환 타입을 보자마자 이건 투포인터구나! 라는 생각을 했다.

그리고 문제에 나와있는대로 모든 종류를 포함해야 한다는 조건때문에 Set과 HashMap을 이용해 중복에 대한 처리를 진행하거나, 갯수에 대한 처리를 진행할 수 있을 것 같다는 생각을 하고 들어갔다.

 

그런데 가장 짧은 이라는 내용을 보고도 뒤에서 더 짧은 구간이 나올 수 있다는 걸 생각하지 못했다. 처음엔 그냥 최초로 나오는 짧은 구간만 확인해서 틀렸었는데, 구조를 조금 바꿔 제대로 코드를 완성했다.

 

투 포인터를 활용한 슬라이딩 윈도우 방식의 풀이:

• start, end 포인터를 두고 진열된 보석 배열을 순회하면서
• Map으로 현재 윈도우 내 보석들의 개수를 관리하고
• 모든 종류의 보석이 윈도우 안에 들어왔을 때마다 최소 길이를 갱신했다.

핵심 포인트는 다음과 같다:

• 전체 보석 종류는 Set으로 미리 계산
• end 포인터를 우측으로 이동하며 Map에 보석을 추가
• 현재 윈도우가 모든 종류를 포함하면, start 포인터를 우측으로 당기며 최소 구간을 갱신하고 불필요한 보석을 제거

 

gems = ["DIA", "RUBY", "RUBY", "DIA", "DIA", "EMERALD", "SAPPHIRE", "DIA"]

보석 종류는 ["DIA", "RUBY", "EMERALD", "SAPPHIRE"]로 총 4개.
가장 짧고 모든 종류를 포함한 구간은 ["RUBY", "DIA", "DIA", "EMERALD", "SAPPHIRE"]

→ 인덱스 3~7

 

start	end	map 상태	모든 보석 포함	최소 길이
1	1	{DIA=1}	✗	∞
1	2	{DIA=1, RUBY=1}	✗	∞
1	3	{DIA=1, RUBY=2}	✗	∞
1	4	{DIA=2, RUBY=2}	✗	∞
1	5	{DIA=3, RUBY=2}	✗	∞
1	6	{DIA=3, RUBY=2, EMERALD=1}	✗	∞
1	7	{DIA=3, RUBY=2, EMERALD=1, SAPPHIRE=1}	✅	7
2	7	{DIA=3, RUBY=1, EMERALD=1, SAPPHIRE=1}	✅	6
3	7	{DIA=3, RUBY=0, EMERALD=1, SAPPHIRE=1} → 제거됨	✗	6

 

최종 결과는 [3, 7]

 

---

코드

import java.util.*;
import java.io.*;

class Solution {
    public int[] solution(String[] gems) {
        Set<String> set = new HashSet<>();
        Map<String, Integer> map = new HashMap<>();
        
        for(int i = 0; i < gems.length; i++){
            set.add(gems[i]);
        }
        
        int start = 0;
        int end = 0;
        int minLength = Integer.MAX_VALUE;
        int answerStart = 0;
        int answerEnd = 0;
        
        while(end < gems.length){
            map.put(gems[end], map.getOrDefault(gems[end], 0) + 1);
            end++;
            
            while(map.size() == set.size()){
                if(end - start < minLength){
                    minLength = end - start;
                    answerStart = start;
                    answerEnd = end;
                }

                map.put(gems[start], map.get(gems[start]) - 1);
                if(map.get(gems[start]) == 0){
                    map.remove(gems[start]);
                }
                start++;
            }
        }
        return new int[]{answerStart+1, answerEnd};
    }
}