투 포인터 활용 - 프로그래머스 보석 쇼핑

문제

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

프로그래머스

 

 

 

문제 접근

• 특정 구간에 모든 종류의 보석들이 포함되어 있는가를 묻는 문제이다.
• 보석들의 진열은 중복된 보석들이 존재할 수 있기 때문에 종류를 파악하기 위해 HashSet을 사용하였다. 또한 구간 내에 존재하는 각 보석의 종류와 그 갯수를 확인하기 위해 HashMap을 사용하였다.
• 투 포인터를 활용하는 곳은 HashMap의 size 즉 현재 구매한 보석의 종류들이 HashSet의 크기, 즉 진열장에 있는 모든 종류의 보석들과 동일한가를 확인한다.
• 만약 그렇지 않고 적다면, 다음 요소를 구매하면 된다. 즉 right를 하나 올린다.
• 만약 동일하다면, 그 지점부터 구간을 하나씩 줄여나간다. 즉 left를 하나 올린다.

import java.util.*;

class Solution {
    public int[] solution(String[] gems) {
        int[] answer = new int[2];
        HashSet<String> set = new HashSet<>();
        
        for(int i = 0; i < gems.length; i++){
            set.add(gems[i]);
        }
        
        int start = 0;
        int end = 0;
        
        HashMap<String, Integer> boughtGem = new HashMap<>();
        int length = Integer.MAX_VALUE;
        
        while(true){           
            if(boughtGem.size() >= set.size()){
                int remainGem = boughtGem.get(gems[start]);
                
                if(remainGem == 1){
                    boughtGem.remove(gems[start]);
                } else{
                    boughtGem.put(gems[start], remainGem - 1);
                }
                
                start++;
            } else if(end >= gems.length){
                break;
            } else{
                boughtGem.put(gems[end], boughtGem.getOrDefault(gems[end], 0) + 1);
                end++;
            }
            
            if(boughtGem.size() == set.size()){
                if(end - start < length){
                    length = end - start;
                    answer[0] = start + 1;
                    answer[1] = end;
                }
            }
        }
        
        return answer;
    }
}

• 쇼핑한 보석들은 각 종류별로 몇개씩 구매되었을 것이다. 만약 여기서 left를 올려 하나씩 뺀다면 해당 보석의 개수가 하나 빠지는 것이고, 그 보석의 개수가 1개였다면 쇼핑목록에서 빠지도록 구현하면 된다.