EunSung.log

보석 쇼핑

4 min read

문제 정보

  • 문제 링크
  • 난이도: Lv.3
  • 문제 유형: 탐색, 슬라이딩 윈도우

풀이

조건을 만족하는 최단 구간을 찾는, 전형적인 슬라이딩 윈도우 문제다.

연속된 부분 수열의 합과 비슷한 문제이지만 윈도우 크기를 줄여야 하는 경우에 대한 판단이 조금 더 어렵다.

우선 구해야 하는 구간의 조건을 살펴보자.

  1. 모든 보석을 하나 이상 포함해야 한다.
  2. 1)을 만족하면서 가장 짧은 구간이어야 한다.

일단 보석이 모두 몇 종류인지 알아야 한다. 이건 Stream을 사용해서 구했다. (Set을 써도 무방)

그리고 1번 조건을 만족하는지 확인하기 위해서는 현재 윈도우 내의 보석이 모두 몇 종류인지 알아야 한다. 다만 구간 내에 보석의 중복이 가능하기 때문에, 구간이 줄어들더라도 보석 종류는 유지될 수 있다. 그래서 HashMap<보석, 개수>을 사용했다.

그런 다음엔 슬라이딩 윈도우를 사용해 gems를 탐색하면 된다.

우선 윈도우 내에 모든 종류의 보석이 포함될 때까지 right를 늘린다. 그러다 모든 보석 종류가 포함되었을 때, 윈도우의 크기가 기존의 구간 크기보다 작으면 답을 갱신한다.

이 때, 더 짧은 구간이 가능한지 확인하기 위해 left를 늘려 윈도우 크기를 줄인다. 구간을 줄여도 1번 조건을 만족한다면, 답을 다시 갱신한다. 이는 while을 사용해 구현했다. 일단 줄여보고, while 조건식을 통해 확인하는 방식이다.

코드

import java.util.*;
 
class Solution {
	public int[] solution(String[] gems) {
		int[] answer = new int[2];
		
		int kind = (int) Arrays.stream(gems).distinct().count(); // 보석의 종류 수
		
		int left = 0;
		int right = 0;
		int size = gems.length + 1;
		Map<String, Integer> gemsInWindow = new HashMap<>();
		
		for (right = 0; right < gems.length; right++) {
			gemsInWindow.put(gems[right], gemsInWindow.getOrDefault(gems[right], 0 ) + 1); // 윈도우에 보석 추가
			
			while (gemsInWindow.size() == kind) { // 윈도우 내 모든 보석이 포함된 경우
				if (right - left + 1 < size) { // 기존 길이보다 작다면 갱신
					answer[0] = left + 1;
					answer[1] = right + 1;
					size = right = left + 1;
				}	
				
				// 더 짧은 구간이 있는지 확인
				// 일단 구간을 줄여보고, while 조건식을 통해 확인하는 방식
				gemsInWindow.put(gems[left], gemsInWindow.get(gems[left]) - 1);
				if (gemsInWindow.get(gems[left]) == 0)
					gemsInWindow.remove(gems[left]);
				left++;		
			}
		}
		
		return answer;
	}
}

백링크