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

programmers.co.kr/learn/courses/30/lessons/67258

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

문제풀이

gems 배열의 크기가 100,000이하 이기때문에 2중 반복문으로 못 풀어서 다른 방향으로 풀려고 노력하였다.

먼저 보석 갯수를 알아야한다. HashSet으로 보석의 갯수를 구한다.

그리고 따로 각 보석의 이름을 Key로 가지고 Value로는 가장 최근 자리를 저장하는 HashMap을 만든다.

길이는 보석의 최소자리와 최대 자리의 +1이 길이이고 저장된 Value에서 Min과 Max를 구해서 길이를 구한다.

마지막으로 최소자리의 보석을 삭제 시켜주고 그 보석이 나타날때 다시 위와 같이 반복한다.

최소자리( 맨 먼저 시작되는 보석 )를 삭제시켜주는 이유는 예시로

["DIA", "RUBY", "RUBY", "DIA", "DIA", "EMERALD", "SAPPHIRE", "DIA"] 길이는 5이기만

마지막 "DIA"가 "RUBY"가 되면 최소 길이는 4가 되기때문에 위와 같은 상황을 최소자리만 삭제 시키고 다시 저장되었을때 구하면 되기 때문이다.

코드

import java.util.*;

class Solution {
    public int[] solution(String[] gems) {
        int[] answer = new int[2];
        
        Set<String> gemCheck = new HashSet<>();
        
        //보석 종류 확인
        for(int i=0; i<gems.length; i++){
            gemCheck.add(gems[i]);
        }
        
        //보석 종류 갯수
        int gemNum = gemCheck.size();
        
        gemCheck.clear();
        HashMap<String, Integer> gemDisplay = new HashMap<>();
        int gemLength = Integer.MAX_VALUE;
        
        for(int i=0; i<gems.length; i++){
            
            gemDisplay.put(gems[i], i+1);
            
            // 모든 종류가 확인 될 때
            if(gemDisplay.size() == gemNum){
                int min = Integer.MAX_VALUE;
                int max = 0;
                String minKey = "";
                
                // 진열된 보석 전시 길이
                for(String key : gemDisplay.keySet()) {
                    if (gemDisplay.get(key) < min){
                        min = gemDisplay.get(key);
                        minKey = key;
                    }
                    max = Math.max(max, gemDisplay.get(key));
                }
                gemDisplay.remove(minKey);
                
                if(max-min+1 < gemLength){
                    gemLength = max-min+1;
                    answer[0] = min;
                    answer[1] = max;
                }
            }
        }
        
        return answer;
    }
}