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

문제

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

프로그래머스

 

---

 

문제 개요

어피치가 보석 매장에서 모든 종류의 보석을 적어도 하나씩 포함하는 가장 짧은 구간을 찾으려 한다. 진열대 번호 순서대로 주어진 보석 배열에서 이러한 구간의 시작과 끝 번호를 반환하는 문제이다.

접근 방법

1. 보석 종류 개수 파악:
   주어진 gems 배열에서 HashSet을 사용해 보석의 고유한 종류 개수를 구한다. 이를 기준으로 구간 내에서 모든 보석 종류를 포함했는지 판단한다.
2. 투 포인터 알고리즘 활용:
   • start와 end 포인터를 사용해 현재 구간을 관리한다.
   • end 포인터를 증가시키며 구간에 포함된 보석을 HashMap에 저장하고 개수를 관리한다.
   • 구간 내 보석의 개수가 중복되는 경우, start 포인터를 오른쪽으로 이동하며 구간을 축소한다.
3. 구간 길이 업데이트:
   • 현재 구간이 모든 보석 종류를 포함하는 경우, 구간 길이를 확인하여 최소 길이인 경우 답을 갱신한다.
   • 시작 번호와 종료 번호는 1부터 시작하므로 반환 시 1을 더한다.
4. 최종 결과 반환:
   모든 가능한 구간을 탐색하며 가장 짧은 구간의 시작과 끝 번호를 반환한다.

 

코드

import java.util.*;
class Solution {
    public int[] solution(String[] gems) {
        int[] answer = new int[2];
        int kind = new HashSet<>(Arrays.asList(gems)).size();
        Map<String, Integer> map = new HashMap<>();
        
        int len = Integer.MAX_VALUE;
        int start = 0;
        
        for(int end=0; end<gems.length; end++) {
            map.put(gems[end], map.getOrDefault(gems[end], 0) + 1);
            
            while(map.get(gems[start]) > 1) {
                map.put(gems[start], map.get(gems[start]) - 1);
                start++;
            }
            if(map.size() == kind && len > (end - start)) {
                len = end - start;
                answer[0] = start + 1;
                answer[1] = end + 1;
            }
        }
        
        return answer;
    }
}