[Java] 모든 종류를 포함하는 최단 구간 구하기

1. 문제

• 배열 gems는 진열되어 있는 모든 보석을 나열한 것
• 모든 보석을 하나 이상 포함하는 최단 구간을 찾아 { 시작 진열대 번호, 끝 진열대 번호 } 형식으로 반환
• 최단 구간이 여러개일 경우 시작 진열대 번호가 가장 작은 구간을 반환

 

2. 해결

• set 이용하여 종류 개수 구하기
• map 이용하여 종류 별로 둘 이상인지 확인
• queue 이용하여 최단 구간 구하기
• 투 포인터 알고리즘 이용 : 우선 구간의 시작점을 고정시킨 후 끝점을 한칸씩 증가시키며 최단 구간을 구한다. 그 다음 시작점을 한칸 증가시켜 앞과 같은 과정을 반복하여 최종적으로 가장 짧은 구간을 구한다. 

import java.util.*;

class GetMinSection {
    public int[] getMinSection(String[] gems) {
        int[] section = new int[2];	// 최단 구간의 시작과 끝 번호 저장
        
        HashSet<String> set = new HashSet<>();	// 보석 종류 저장
        HashMap<String, Integer> map = new HashMap<>();	// 종류별로 보석이 몇 개 인지 저장
        Queue<String> q = new LinkedList<>();	// 최단 구간에 포함되는 보석 순서대로 저장
        
        // 보석의 종류 찾기
        for(String s : gems) {
            set.add(s);
        }
        
        int len = gems.length;	// 최단 구간의 길이를 저장 - 초기값은 진열대의 길이(가장 큰 값)
        int start = 0;	// 큐에 들어간 첫번째 요소를 가리킴
        int startPoint = 0;	// 최단 구간의 시작점
        
        // 진열대의 보석을 큐에 순서대로 삽입하면서 모든 종류를 포함하는 최단 구간인지 검사
        for(int i = 0; i < gems.length; i++) {
            q.offer(gems[i]);
            map.put(gems[i], map.getOrDefault(gems[i], 0) + 1);	// 종류별로 보석의 개수 저장            
            
            while(true) {
                // 큐에 들어있는 첫번째 보석이 마지막 보석과 같은 경우 
                String temp = q.peek();                
                if(map.get(temp) > 1) {	
                    // 첫번째 보석을 큐에서 삭제
                    q.poll();
                    map.put(temp, map.get(temp) - 1);
                    
                    start++; // 최단 구간의 시작점을 한칸 증가
                }
                else {
                    break;
                }
            }
            
            // 모든 종류의 보석을 포함하고 새로운 최단 구간을 찾은 경우
            if(map.size() == set.size() && q.size() < len) {
                len = q.size();	// 새로운 최단 구간의 길이 저장
                startPoint = start;	// 새로운 최단 구간의 시작점 저장
            }
        }
        
        section[0] = startPoint + 1;	// 최단 구간의 시작번호
        section[1] = startPoint + len;	// 최단 구간의 끝번호
        
        return section;
    }
}