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

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

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

import java.util.*;

class Solution {
    public int[] solution(String[] gems) {
        int[] answer =new int[2];
        Set<String> s=new HashSet<>();
        Map<String, Integer> basket=new HashMap<>();
        List<Range> ans=new ArrayList<>();  
        int end=0;
        for (String g: gems){
            s.add(g);
        }
        for (int start=0; start<gems.length; start++){
            while (basket.keySet().size()<s.size() && end<gems.length){
                int val=basket.containsKey(gems[end])?basket.get(gems[end])+1:1;
                basket.put(gems[end], val);
                end++;
            }
            if (basket.keySet().size()==s.size()){
                ans.add(new Range(start+1,end));
            }
            basket.put(gems[start], basket.get(gems[start])-1);
            if (basket.get(gems[start])==0){
                basket.remove(gems[start]);
            }
        }
        Collections.sort(ans);
        answer[0]=ans.get(0).start;
        answer[1]=ans.get(0).end;
        return answer;
    }
    
    
    public static class Range implements Comparable<Range>{
        public int start, end;
        public Range(int start, int end){
            this.start=start;
            this.end=end;
        }
        @Override
        public int compareTo(Range r){
            if (this.end-this.start>r.end-r.start){
                return 1;
            }
            else if ((this.end-this.start)==(r.end-r.start)){
                if (this.start>r.start){
                    return 1;
                }
            }
            return -1;
        }
    }
}

투포인터를 이용하는 문제. 투포인터의 경우 시간복잡도가 O(N)이다.

처음엔 basket을 set 으로 하려고 했으나.. 이 방법에 심각한 오류가 있다는걸 깨달음..(기존 start 삭제해주고 다음 start로 옮겨갈 때 구간에 속한 애들도 삭제될 수 있다는 오류..)

자료구조를 map으로 바꿔서 처리했다. keySet 크기가 못미칠때는 map의 key에 해당하는 value를 증가시킨다.

start 를 옮길 때에는 map의 value 값을 빼주고, 0이 나올 경우 해당 key를 삭제해주는 방식으로 구간을 옮겼다.

 

key가 없으면 0, 아니면 value 리턴하는 함수: map.getOrDefault(gems[right], 0)

default V getOrDefault(Object key,
                       V defaultValue)

Returns the value to which the specified key is mapped, or defaultValue if this map contains no mapping for the key.

 

그리고 객체를 생성해서 comparable을 구현할 필요 없이,

어차피 탐색을 앞쪽부터 시작하므로 range의 크기가 minValue보다 작은게 나올때 start, end를 갱신해주는 방식을 취할 수 있다.