[프로그래머스] 보석 쇼핑 Java 풀이 및 해설

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

프로그래머스

풀이 방법

start와 end 두개의 위치를 이용해 푼다.

 

start는 다음과 같은 상황일때 갱신된다.

• start ~ end에 start 위치의 보석이 2개이상일 경우 ( 모든 종류의 보석을 start ~ end 에 포함하고 있을 때 )
  • start의 위치를 +1하면 모든 종류의 보석을 포함하며 최소 길이가 될 수 있다.

end는 반복문을 돌며 0부터 끝까지 돌아주면된다.

이때 start를 갱신할 수 있다면 갱신해주면 된다.

그러면 길이는 최소로 되며 시작 진열대의 번호가 가장 작은 구간을 구할 수 있다.

 

전체 코드

import java.util.*;
class Solution {
    public int[] solution(String[] gems) {
        int[] answer = new int[2];
        
        Set<String> kind = new HashSet<String>();
        for(int i=0; i<gems.length; i++) {
            kind.add(gems[i]);
        }
        
        int start = 0;
        int len = 100001;
        Map<String, Integer> m = new HashMap<>(); // (보석 명, 개수)
        for(int end = 0; end<gems.length; end++) {
            
            if(m.get(gems[end]) == null) {
                m.put(gems[end], 1);
            } else {
                m.put(gems[end], m.get(gems[end])+1);
            }
            
            // start 위치의 보석이 2개 이상 포함되어 있다면 start 위치의 보석을 빼고 한칸 오른쪽으로 이동이 가능함
            // 이동해도 모든 보석을 포함하며 길이가 최소가 될 수 있기 때문임
            while(m.get(gems[start]) > 1) {
                m.put(gems[start], m.get(gems[start])-1);
                start++;
            }
            
            // 모든 종류를 포함하고 있으며 길이가 최소로 갱신할 수 있다면
            if(m.size() == kind.size() && (end - start + 1) < len) {
                answer[0] = start+1;
                answer[1] = end+1;
                len = end - start + 1;
            }
        }
        
        return answer;
    }
}