카카오 2020 여름 인턴십 보석 쇼핑

현재 풀이이다. 

정확도는 맞는데 효율성 테스트는 죽어도 통과가 안된다..

찾아보니 "슬라이딩 윈도우" 라는 알고리즘을 이용하여 풀어야한다고 한다.

조금 알아본 바로는 for문 2개가 아닌 

이전 윈도우와 다음 윈도우의 중복은 그대로 사용하고 

이전에서 다음으로 넘어오면서

이전에 사용했지만 다음에는 사용되지 않는것을 빼고

이전에는 사용하지 않았지만 다음에는 사용하는 것을 더하면서

알고리즘을 구성해야한다는 것 같다...

import java.util.HashMap;
import java.util.HashSet;

public class kakao_2020_보석쇼핑 {

	public static void main(String[] args) {

//		String[] gems = { "DIA", "RUBY", "RUBY", "DIA", "DIA", "EMERALD", "SAPPHIRE", "DIA" };
		String[] gems = { "ZZZ", "YYY", "NNNN", "YYY", "BBB" };
//		String[] gems = { "AA", "AB", "AC", "AA", "AC" };
		solution(gems);
	}

	public static int[] solution(String[] gems) {
		int[] answer = new int[2];
		HashMap<String, Integer> hm = new HashMap<>();
		int idx = 0;
		for (int i = 0; i < gems.length; i++) {
			if (!hm.containsKey(gems[i])) {
				hm.put(gems[i], idx);
				idx++;
			}
		}

		int minV = gems.length;
		int memory = -1;

		for (int i = 0; i <= gems.length - hm.size(); i++) {
			HashSet<String> hs = new HashSet<>();
			if (i + minV <= gems.length) {
				for (int j = i; j < i + minV; j++) {
					hs.add(gems[j]);
					if (hs.size() == hm.size()) {
						if (minV > (j - i)) {
							minV = j - i;
							memory = i;
						}
						break;
					}
				}
			}
		}
		System.out.println(memory + " " + minV);
		answer[0] = memory + 1;
		answer[1] = memory + minV + 1;
		System.out.println(answer[0] + " " + answer[1]);
		return answer;
	}
}

blog.fakecoding.com/archives/algorithm-slidingwindow/

[알고리즘] 슬라이딩 윈도우 알고리즘