[Programmers] 보석 쇼핑

2020 카카오 인턴 3번 문제였다.

이 문제를 맨처음 봤을 때 배열 크기 N의 범위때문에 어떻게 접근할까 고민을 하였다. 최대 100000이기 때문에 2중 포문만 되어도 시간초과가 발생하기에 이분탐색을 떠올렸다. 이분 탐색을 이용하여 문제를 풀었을 때 기본 테스트 케이스는 통과하였지만 효율성검증에 있어 탈락을 하였다. 그래서 이분 탐색 후 checking하는 과정에서 배열에서의 고정길이 탐색을 효율적으로 할 수 있는 슬라이딩 윈도우 알고리즘을 사용하였다.

이 문제는 배열에서의 조건을 만족하는 최소길이를 찾는 문제이므로 크게 두가지 방법을 사용할 수 있다. 첫째로, 길이를 이분탐색으로 구하고, 그 고정길이를 이용하여 슬라이딩 윈도우를 사용하는 방법이 있다. 두번째로, 고정길이의 탐색이 아닌 가변길이 탐색인 투포인터 알고리즘이 있다.

즉, 이분탐색 + 슬라이딩 윈도우 or 투포인터 를 이용하여 풀 수 있었던 문제이다.

package programmers;
 
import java.util.Arrays;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Set;
 
import javax.naming.spi.DirStateFactory.Result;
import javax.swing.plaf.synth.SynthSplitPaneUI;
 
 
public class Solution_2020카카오인턴_보석쇼핑 {
    public static void main(String[] args) {
//                String[] gems= {"DIA", "RUBY", "RUBY", "DIA", "DIA", "EMERALD", "SAPPHIRE", "DIA"};
//                String[] gems= {"AA", "AB", "AC", "AA", "AC"};
//                String[] gems= {"XYZ", "XYZ", "XYZ"};
        String[] gems= {"ZZZ", "YYY", "NNNN", "YYY", "BBB"};
        System.out.println(Arrays.toString(solution(gems)));
    }
 
    static int[] solution(String[] gems) {
 
        Set<String> set=new HashSet<>();
        Set<String> temp = new HashSet<>();
 
        Map<String, Integer> map=new HashMap<>();
 
        for(String gem : gems) {
            set.add(gem);
        }
        int target= set.size();
 
        int left=1;
        int right=gems.length;
 
        int[] answer=new int[2];
 
 
        while(left<=right) {
 
 
            map=new HashMap<>();
            temp=new HashSet<>();
            
            for(String gem : gems) {
                map.put(gem,0);
            }
 
            int mid=(left+right)/2;
            boolean check=false;
 
            int start=0;
            int end=0+mid-1;
 
            for(int j=start;j<=end;j++) {
                map.put(gems[j], map.get(gems[j])+1);
                temp.add(gems[j]);
            }
 
            if(temp.size()==target) {
                check=true;
            }
 
            if(check==false) {
                while(true) {
                    if(map.get(gems[start])-1==0) {
                        map.put(gems[start], 0);
                        temp.remove(gems[start]);
                    }else {
                        map.put(gems[start], map.get(gems[start])-1);
                    }
 
                    start=start+1;
                    if(start==gems.length)
                        break;
                    
                    end=end+1;
                    if(end == gems.length)
                        break;
                    map.put(gems[end], map.get(gems[end])+1);
                    temp.add(gems[end]);
 
                    if(temp.size()==target) {
                        check=true;
                        break;
                    }
                }
            }
 
            if(check==true) {
                right=mid-1;
                answer[0]=start+1;
                answer[1]=end+1;
            }else {
                left=mid+1;
            }
        }
        return answer;
    }
}