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

문제 링크 - https://school.programmers.co.kr/learn/courses/30/lessons/67258#

🌱 문제

🌱 풀이

• 백준의 '회전 초밥' 문제와 비슷하게 푸는 투포인터 문제였다.
  1) Set에 gems 보석들을 넣고 set.size()를 통해 종류의 갯수를 알아낸다.
  2) 인덱스로 left,right를 한칸씩 이동해 간다. HashMap<String, Integer>를 이용하여 보석 전체 종류를 만족하면서 left와 right 차이가 가장 작을때를 체크해준다.
• 이때, 이전의 diff보다 현재의 diff가 작을 때만 정답배열을 갱신하기 때문에 자동으로 , 만약 가장 짧은 구간이 여러 개라면 시작 진열대 번호가 가장 작은 구간을 return 합니다.라는 조건을 만족할 수 있게 된다.

헷갈렸던 부분

• while(true)로 선언된 반복문을 언제 break해야할지가 가장 헷갈렷다.
• 처음에는 막연하게 right가 끝까지 갔을때 break를 하면 된다고 생각했다. 하지만 그렇게 하면 다음과 같은 예외가 있다. 주어진 배열 = ['A','A','B']일때 정답은 [2,3]이지만 [1,3]이 나와버린다.
• 그러므로 언제 break를 할지를 잘 고려해야 했는데 set.size()!=map.size()이면서 right==n일때를 break 걸어주었다. 왜냐하면 right가 끝까지(n)갔는데 set.size()!=map.size()라는 것은 더이상 left를 증가시키는것도 의미가 없기 때문에 종료하면 되기 때문이다. (이 부분은 너무 헷갈려서 구글링을 참고했다.)

🌱 코드

import java.util.*;

class Solution {
    public int[] solution(String[] gems) {
        int[] answer = new int[2];
        int n = gems.length;
        HashSet<String> set = new HashSet<String>();
        for(String s : gems){
            set.add(s);
        }
        int cnt = set.size();
        System.out.println("cnt: "+cnt);
        
        
        int left=0;
        int right=0;
        int startIndex=0;
        int endIndex=0;
        int diff=Integer.MAX_VALUE;
         
        //현재 범위에서(left~right) 각 보석의 갯수를 확인할 때 사용할 map
        HashMap<String, Integer> map = new HashMap<String,Integer>();

        while(true){
           if(set.size()==map.size()){  // set의 사이즈가 map과 같으면 left를 오른쪽으로 이동 
                
                // left에있는 보석갯수 하나 줄이기.
                // 이때는 left에 해당하는 보석이 무조건 map에 존재하므로 그냥 1감소 시키면 됨.
                map.put(gems[left],map.get(gems[left])-1);
                
                // 범위에 존재하지 않으면 map에서도 빼주기
                if(map.get(gems[left])==0)
                    map.remove(gems[left]); // key이름 지정해서 찾아주면 됨.
                
                left ++; // left 증가
                
            }else if(right==n){ // right==n인 경우는 left를 증가시킬 일만 남았는데 set size가 아니라면 더이상 left 증가가 의미없기 때문에 끝내주기
               break;
               
           }else{  // set.size()!=map.size() 
                // right 증가시키기 
              
                map.put(gems[right],map.getOrDefault(gems[right],0)+1);
                right++; 
            }
            
            if(set.size()==map.size()){ // left, right의 이동이 한번 끝날때마다 해당 범위가 모든 보석을 포함한 범위인지, 그렇다면 길이는 더 짧은지 검사 
                    if((right-1)-left<diff){
                        startIndex=left;
                        endIndex=right-1;
                        diff=(right-1)-left;
                    }
                }

        }
        answer[0]=startIndex+1;
        answer[1]=endIndex+1;
        return answer;
    }
}