[java] 프로그래머스 - 보석 쇼핑

문제

프로그래머스-보석 쇼핑
보석 진열장에서 모든 보석을 하나 이상 포함하며 가장 짧은 구간을 찾는 문제.
투 포인터로 풀 수 있다

• 제한 사항
  gems 배열의 크기는 1이상 100,000 이하다
  가장 짧은 구간이 여러 개라면 시작 진열대 번호가 가장 작은 구간을 리턴한다

• 예시
  gems : [“DIA”, “RUBY”, “RUBY”, “DIA”, “DIA”, “EMERALD”, “SAPPHIRE”, “DIA”]
  3번부터 7번까지 (“RUBY”, “DIA”, “DIA”, “EMERALD”, “SAPPHIRE”)가 모든 보석을 포함하며 가장 짧은 구간이다

정답을 출력할 때 배열의 번호가 0부터가 아닌 1부터 시작한다고 생각하고 답을 출력해야 한다

풀이

투 포인터 알고리즘을 응용해서 풀 수 있는 문제다

먼저 set을 사용해서 보석의 중복을 제거한 갯수를 구한다
만약 set의 크기가 1이라면 보석은 1종류이므로 [1,1]을 출력하고 종료한다

set의 크기가(보석의 종류가) 1이 아니라면 투 포인터 알고리즘으로 가장 짧으면서 보석의 종류를 다 포함하는 구간을 찾는다

먼저 start, end를 0으로 놓는다
가장 짧은 길이를 확인하기 위한 변수 min와 같은 길이에서 작은 인덱스를 위해 minStart도 둔다

start는 시작 구간, end는 end-1까지 포함한다는 뜻으로 사용했다

현재 길이가 min(최소길이)보다 크거나 end가 배열의 끝에 닿아있으면
start에 포함된 보석을 제거하고 start를 오른쪽으로 1칸 이동시킨다

위의 조건이 아니라면 end위치의 보석을 포함하고 end를 오른쪽으로 1칸 이동시킨다

만일 현재 구간에 포함된 보석의 가짓수가 set의 길이(보석 종류)와 같다면
최소길이인지 판별한다
최소길이보다 같다면 현재 start와 minStart를 비교해 작은값을 저장한다
최소 길이보다 작다면 min을 갱신하고 start를 minStart에 저장한다

반복문 종료 후 [minStart,minStart+min]을 리턴한다

소스코드

import java.util.*;
class Solution {
	static Set<String> set;
	static Map<String, Integer> chk;

	public int[] solution(String[] gems) {
		set = new HashSet<>(); // 보석의 가짓수
		chk = new HashMap<>(); // 현재 구간의 보석 수

		int[] answer = new int[2]; // 정답용
		// 보석을 set에 넣어 중복제거
		for (int i = 0; i < gems.length; i++) { 
			if (!set.contains(gems[i])) {
				set.add(gems[i]);
			}
		}
		// 보석 수가 1개라면 [1,1] 리턴
		if (set.size() == 1) {
			answer[0] = 1;
			answer[1] = 1;
			return answer;
		}

		int start = 0;
		int end = 0;
		int min = gems.length; // 최소길이
		int minStart = gems.length; // 최소길이일때의 최소 시작위치

		while (start < gems.length) {
			if (end - start + 1 > min || end == gems.length) {
				remove(gems[start]); // start위치의 보석 제거
				start++;
			} else {
				// end 위치 보석 추가
				add(gems[end]);
				end++;
			}
			if (chk.size() == set.size()) { // 모든 보석을 포함한 경우
				if (end - start < min) { // 최소길이 갱신
					min = end - start;
					minStart = start;
				} else if (end - start == min) { // 최소 시작위치 갱신
					if (minStart > start)
						minStart = start;
				}
			}
		}
		answer[0] = minStart + 1;
		answer[1] = answer[0] + min - 1;
		return answer;
	}

	private void add(String str) { // chk에 보석 추가
		if (!chk.containsKey(str))
			chk.put(str, 1);
		else
			chk.put(str, chk.get(str) + 1);
	}

	private void remove(String str) { // chk에 보석 제거
		if (chk.get(str) == 1)
			chk.remove(str);
		else
			chk.put(str, chk.get(str) - 1);
	}
}