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

코딩테스트 연습 - 보석 쇼핑 | 프로그래머스 (programmers.co.kr)

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

어떻게 생각하고 문제를 풀었는가?

가장 짧은 구간을 구하기 위해서는 전체 보석의 종류를 알아야 하고, 어떤 위치에서 시작했을 때 구간의 길이가 몇인지 확인해야 합니다.

시작 위치는 1번째 보석부터 차례대로 이동하므로 FIFO인 자료구조 Queue에서 원소가 지워지는 과정과 비슷하게 볼 수 있으며, 순서대로 원소를 삽입하면서 Queue에 삽입된 원소의 종류가 전체 보석의 종류와 비슷한 순간을 확인하고 시작 위치를 이동시킬 수 있습니다.

Queue에서 원소를 삭제할 때 Queue에 담긴 보석의 종류가 보존되는지 확인이 필요합니다.

따라서 HashMap에 각 보석의 개수를 저장, 원소의 삭제마다 보석의 수를 차감하면서 이를 확인할 수 있습니다.

코드

import java.util.*;
class Solution {
    public int[] solution(String[] gems) {
        Queue<String> queue = new LinkedList<>();
        HashMap<String, Integer> map = new HashMap<>();
        int length = gems.length;
        for(int i=0; i<gems.length; i++){
            map.put(gems[i],0);
        }
        int maxkinds = map.size();
        int start=0, answer=0, kinds=0;
        for(int i=0; i<gems.length; i++){
            int count = map.get(gems[i]);
            if(count==0) kinds++;
            map.put(gems[i],count+1);
            queue.offer(gems[i]);
            if(kinds!=maxkinds) continue;
            String str = queue.peek();
            while(map.get(str)>1){
                map.replace(str,map.get(str)-1);
                start++;
                queue.poll();
                str = queue.peek();
            }
            if(length > queue.size()){
                answer = start;
                length = queue.size();
            }
        }
        return new int[] {answer+1, answer+length};
    }
}

최대 구간의 길이는 주어진 입력 배열의 크기입니다.

for문으로 queue 삽입과 HashMap value값 증가를 하며 HashMap에 해당 문자열이 처음 카운트되었다면 종류를 카운트하는 방식으로 시작 위치를 옮겨도 되는지 확인할 수 있습니다.

Queue의 첫 원소를 key로 갖는 HashMap value값이 2 이상인 경우 시작 위치를 옮겼을 때 종류가 유지된다고 생각할 수 있으므로 이때 시작위치를 이동할 수 있습니다.

모든 원소를 queue에 삽입한 후 최단 거리를 갖는 시작위치를 찾고, 마지막 위치를 시작위치 + 최단 구간의 길이로 구할 수 있습니다. 이때 시작위치 answer는 0부터 N-1로 정해져 있으므로 answer+1을 하여야 합니다.