java 프로그래머스 lv3 보석쇼핑 | sliding window + map 활용

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

프로그래머스

 

# 문제 풀기 전 고민하기 

 

1. 물건을 싹쓸이 하는 습관이 있다. 범위 안에서 특정 구간이 빠지면 안된다. 

-> 범위 length를 정해놓고 범위 앞에 있는 인덱스 값을 빼고 범위 뒤에있는 다음 인덱스 값을 더하면서 확인해가는 슬라이딩 윈도우를 생각함 

 

2. 모든 종류의 보석을 적어도 하나 이상은 다 포함시켜야 함 

-> 보석 종류가 어떤게 있는지 input배열을 중복을 제거하는 Set 자료구조를 활용해야겠다고 생각함 

 

3. 효율성 테스트가 있고 input 배열의 크기는 십만까지 가능함 

-> 그냥 for문 두개로 input배열을 하나하나 접근해서 확인하다간 십만 * 십만 = 터짐

-> 그럼 현재 범위만큼 copyOfRange로 input 배열을 자르고 얘를 또 다른 set에 넣어서 보석종류를 넣은 set과 containsAll로 확인할까? 

-> containsAll도 결국 하나하나 비교하는거잖아 이것도 터짐 

-> 얘를 어떻게 처리할까? 

 

 

# 제출코드

public int[] solution(String[] gems) {
	int[] answer = new int[2];
 	// 전체 상품 종류 수 확인을 set으로 확인
	Set<String> products = new HashSet<>(Arrays.asList(gems));
	Map<String, Integer> gemCount = new HashMap<>();
	int start = 0;// 윈도우 시작 위치
	int range = gems.length;// 최소 범위 길이 저장

	//윈도우 끝 위치를 증가시켜나감
	for (int end = 0; end < gems.length; end++) {
		gemCount.put(gems[end], gemCount.getOrDefault(gems[end], 0) + 1);
            
		// 모든 보석 개수를 포함하고 있는 범위를 찾으면
		while (gemCount.size() == products.size()) {
			// 기존 범위보다 작은 범위인 경우 answer 변수에 업데이트
			if (range > end - start) {
				range = end - start;// 기존 범위 값 업데이트
				answer[0] = start + 1;
				answer[1] = end + 1;
			}
			// start 증가해서 윈도우의 사이즈를 줄이기 전에 시작위치의 보석 개수를 감소
			gemCount.put(gems[start], gemCount.get(gems[start]) - 1);
			if (gemCount.get(gems[start]) == 0) {// 0이 되어버리면 보석 목록에서 제거
				gemCount.remove(gems[start]);
			}

			start++;// 윈도우의 시작위치 증가
		}
	}

	return answer;
}

 

윈도우의 범위(크기)를 input 배열의 전체길이로 잡아놓고, 보석 전체종류가 있으면서 && 더 작은 범위를 발견하면 해당 인덱스 위치를 정답 배열에 저장하고 비교할 윈도우의 범위를 갱신한다.

 

보석 전체 종류가 있는 경우의 인덱스 end 범위를 찾으면 0으로 설정한 인덱스 시작 위치를 서서히 증가시키면서 범위를 줄였는데도 보석 종류를 전부 다 포함하고 있는지를 계속해서 확인해간다. 

 

Map은 key와 value구조 쌍을 이루고 있는데, key는 중복이 불가능하다.

따라서 key를 보석이름으로 만들어 저장하면 해당 map의 사이즈가 곧 보석 종류의 수로 전체 종류를 포함하고 있는지를 확인할 수 있다.

 

이렇게 map의 size로 모든 보석 종류를 포함하고 있는지를 확인하기 때문에, start인덱스 증가로 확인해야 할 범위가 바뀌면 이전 범위에 해당해서 넣어놨던 보석을 계속 뺴줘야한다. 

 

따라서 map의 value로는 범위에 해당하는 보석의 등장 횟수를 저장해서 시작인덱스에 해당하는 보석의 수를 빼준다. input으로 들어오는 보석이 중복으로 들어오기 때문에 등장횟수가 0이되면 map에서 해당 key를 제거하여 While 문을 빠져나오도록 한다. 

 

이렇게 map과 슬라이딩 윈도우를 활용해서 제출 했고 정확도와 효율성 모두 통과했다. (메모리: 82.6 MB, 시간: 70.68 ms)

 

 

# 확인을 위해 추가한 TC

혹시 특정 케이스 통과가 안될 경우 위의 테스트케이스를 추가해보자