[알고리즘/투 포인터] 2020 카카오 인턴십 - 보석 쇼핑

본래 알고리즘 문제 같은 경우 따로 올리지 않으려 했지만, 꼭 알고 넘어가고 싶은 의미에서 올려봅니다.

 

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

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

이 문제도 투 포인터 기법을 활용한 방법으로 이 방법을 활용해야 효율성을 통과할 수 있습니다.

투 포인터 기법이란 아래 글에서 확인하시기 바랍니다

mhwan.tistory.com/57

[알고리즘/투포인터] 투포인터 알고리즘

 

이 문제의 경우 end와 start가 끝날때까지 살펴보는 것이 중요하다. 그 이유는 테스트 케이스 6, 7번 때문인데, 해당 반례는

["A", "B", "B", "C", "A"]의 경우 정답은 3, 5가 나와야하나 종료조건이 다르다면 1, 4를 반환할 가능성이 높다.

즉, 반복문의 종료조건은 start == MAX_SIZE && end == MAX_SIZE가 되어야 하며,

start를 증가시키는 경우 : 보석을 모두 포함하고 있거나, end를 증가 시킬 수 없을 때이다. (이 경우 현재 start가 가리키는 보석을 제거하고, start를 증가시킨다.)

      -> 이 때의 경우 보석을 모두 포함한다는 조건이 충족하면 거리가 더 짧거나 start가 더 작을때 갱신을 해줘야한다.

end를 증가시키는 경우 : 조건이 충족되지 않고 end를 증가시킬 수 있는 경우이다. (이 경우 현재 end가 가리키는 보석을 추가해주고, end를 증가시킨다)

 

이렇게 start, end-1까지의 범위의 보석을 hashmap을 통해 넣었다가 제거했다가를 반복하며, 모든 보석이 담겨 있을 경우 start, end를 비교하며 갱신해주면 되는 것이다.

 

# 소스코드

package Kakao;
 
import java.util.Arrays;
import java.util.HashMap;
import java.util.HashSet;
 
public class JewerlyShop2 {
    public static void main(String[] args) {
        System.out.println(Arrays.toString(new JewerlyShop2().solution(new String[]{"ZZZ", "YYY", "NNNN", "YYY", "BBB"})));
    }
    public int[] solution(String[] gems) {
        HashSet<String> gemsSet = new HashSet<>(Arrays.asList(gems));
        HashMap<String, Integer> gemMap = new HashMap<>();
        int start = 0;
        int end = Integer.MAX_VALUE;
 
        int MAX_SIZE = gems.length;
        int tmpStart = 0;
        int tmpEnd = 0;
 
       
        while (true) {
            if (tmpStart < MAX_SIZE && (gemMap.size() == gemsSet.size() || tmpEnd == MAX_SIZE)) {
                //조건이 충족할 때
                if (gemMap.size() == gemsSet.size()) {
                    if ((tmpEnd - tmpStart) < (end - start)) {
                        end = tmpEnd;
                        start = tmpStart;
                    } else if ((tmpEnd - tmpStart) == (end - start)) {
                        if (tmpStart < start) {
                            start = tmpStart;
                            end = tmpEnd;
                        }
                    }
                }
                int cnt = gemMap.get(gems[tmpStart]) - 1;
                if (cnt >= 1) {
                    gemMap.put(gems[tmpStart], cnt);
                } else {
                    gemMap.remove(gems[tmpStart]);
                }
 
                tmpStart++;
            } else if (tmpEnd < MAX_SIZE){
                gemMap.put(gems[tmpEnd], gemMap.getOrDefault(gems[tmpEnd], 0)+1);
                tmpEnd++;
            }
 
 
            if (tmpStart == MAX_SIZE && tmpEnd == MAX_SIZE)
                break;
        }
 
        return new int[]{start+1, end};
    }
}