문제 바로가기

접근방식

처음에는 완전탐색을 써야하나? 고민하다 투포인터 / 윈도우슬라이싱문제라는 것을 알고 들어갔다.
기본적으로 set을 쓰고 인덱스 start, end만들어서 움직이면서 접근했다.

import java.io.*;
import java.util.*;

class Solution {
    public int[] solution(String[] gems) {
        int[] answer = new int[2];
        
        HashSet<String> set=new HashSet<>();
        for(String gem:gems){
            set.add(gem);
        }
        
        int start=0;
        int end=0;
        int len=100001;
        while(start<=end){
            HashSet<String> temp=new HashSet<>();
            if(start==end){
                temp.add(gems[start]);
            }else{
                for(int i=start;i<end;i++){
                    temp.add(gems[i]);
                }
            }
            if(temp.containsAll(set)){
                if(end-start<len){
                    len=end-start;
                    answer[0]=start+1;
                    answer[1]=end+1;
                }
            }
            
            if(end==gems.length-1){
                start++;
            }else{
                end++;
            }
        }
        
        return answer;
    }
}

이렇게 풀었는데 틀렸다.

알고보니 if(temp.containsAll(set))이 조건을 만족할때도 start를 늘려줘야했다.
나는 단순히 end를 끝까지 늘리고, end가 끝에 다다르면 그제서야 start를 늘리는 식으로 접근했었는데, 그러면 end가 중간값일때 start는 0에만 고정되어있어 최소값을 찾지 못할 수도 있다.

고쳤으나 시간초과

import java.io.*;
import java.util.*;

class Solution {
    public int[] solution(String[] gems) {
        int[] answer = new int[2];
        
        HashSet<String> set=new HashSet<>();
        for(String gem:gems){
            set.add(gem);
        }
        
        int start=0;
        int end=0;
        int len=100001;
        while(start<=end){
            HashSet<String> temp = new HashSet<>();
            for(int i=start;i<=end;i++){
                temp.add(gems[i]);
            }
            if(temp.containsAll(set)){
                if(end-start<len){
                    len=end-start;
                    answer[0]=start+1;
                    answer[1]=end+1;
                }
                start++;
            }else{
                if(end<gems.length-1){
                    end++;
                }else{
                    start++;
                }
            }
        }
        
        return answer;
    }
}

정답은 맞으나...! 효율성에서 전부 시간초과나버렸다.
이유를 몰라서 지피티한테 물어보니까

while(...)
    HashSet<String> temp = new HashSet<>();
    for(int i=start;i<=end;i++){
        temp.add(gems[i]);
    }

이 부분때문이라고 한다. O(N²)
그래서 temp 해시셋배열을 매번 새로만드는게 아니라 슬라이딩윈도우처럼 하나씩 추가/제거해야한다고 한다.

정답코드

import java.io.*;
import java.util.*;

class Solution {
    public int[] solution(String[] gems) {
        int[] answer = new int[2];
        
        HashSet<String> set=new HashSet<>();
        for(String gem:gems){
            set.add(gem);
        }
        int total=set.size();
        
        int start=0;
        int end=0;
        int len=100001;
        HashMap<String,Integer> map=new HashMap<>();
        while(end<gems.length){
            map.put(gems[end],map.getOrDefault(gems[end],0)+1);
            
            while(map.size()==total){
                if(end-start<len){
                    len=end-start;
                    answer[0]=start+1;
                    answer[1]=end+1;
                }
                
                map.put(gems[start],map.get(gems[start])-1);
                if(map.get(gems[start])==0) map.remove(gems[start]);
                
                start++;
            }
            
            end++;
        }
        
        return answer;
    }
}

결국 해시맵을 써야했다. ㅠㅠ
O(N)