Programmers 67258: 보석 쇼핑

문제 조건 

1. 진열된 모든 종류의 보석을 적어도 1개 이상 포함하는 가장 짧은 연속된 구간을 찾아서 구매
2. 가장 짧은 구간이 여러 개라면 시작 진열대 번호가 가장 작은 구간을 리턴

 

 

연속된 구간을 보는 것이기 때문에 투 포인터를 사용하여 풀면 된다고 생각했다.

진열대 위치를 쭉 훑으면서 맵에 저장되어있는 보석의 수가 1보다 크면 시작 위치를 하나씩 땡기는 방법으로 생각하고 문제를 풀었다. 

import java.util.*;
class Solution {
	public int[] solution(String[] gems) {
		int[] answer = new int[2];

		HashMap<String, Integer> selects = new HashMap<String, Integer>();
		HashSet<String> allGems = new HashSet<String>();

		int length = gems.length;
		answer[0] = 1;
		answer[1] = length;

		for (int i = 0; i < length; i++) {
			allGems.add(gems[i]);
		}
		int size = allGems.size();

		int start = 0;
		for (int end = 0; end < length; end++) {
			selects.put(gems[end], selects.getOrDefault(gems[end], 0) + 1);

			while (selects.getOrDefault(gems[start], 0) > 1) {
				selects.replace(gems[start], selects.get(gems[start]) - 1);
				start++;
			}

			if (selects.size() == size && answer[1] - answer[0] + 1 > end - start + 1) {
				answer[1] = end + 1;
				answer[0] = start + 1;
			}
		}

		return answer;
	}
}