보석 쇼핑 [자바]

 

🧫 문제 분석

✔️ 출처

보석 쇼핑 level 3

📖 문제

 

투 포인터 문제로 

모든 종류의 보석을 포함하는 가장 짧은 연속된구간을 찾는 문제다.

 

먼저 문제에서 보석의 종류의 개수를 알려주지 않으므로 따로 카운트한다.

map 자료구조를 사용해서 현재 까지 구간에 어떤 보석이 몇개씩 있는지 저장하면서 체크한다.

 

현재 구간의 보석 종류 개수가 모든 보석의 종류 개수와 같다면

구간 줄이기를 시도한다.

 

현재 앞쪽 포인터 (start)에 있는 보석이 map에서 개수가 1개면 오히려 구간을 늘려서 

다음 탐색때 더 줄 일 가능성을 늘린다.

 

1개가 아니라면 s를 한칸 더 땡겨서 구간을 줄이는 식으로 풀어나간다.

 

테스트 케이스

A B B C D A
s       e

처음에는 여기까지 탐색하고 

map.size() == 모든 보석 종류 개수이므로

구간을 줄일 수 있는지 확인한다.

 s포인터에 있는 A가 현재 담은 구간에 개수가 1개이므로 줄일 수 없다. 따라서

구간을 오히려 더 늘려서 기회를 늘린다.

 

A B B C D A
s         e

이제 s포인터를 체크해보면 A가 2개이므로 구간을 줄일 수 있다.

한 칸 줄인 후 B도 2개이므로 한칸 줄인다.

 

A B B C D A
    s     e

더 이상 구간을 줄일 수도 늘릴 수도 없으므로 

[3,6]이 정답이 된다.

---

🔅 문제 풀이

import java.util.*;

class Solution {
    public int[] solution(String[] gems) {
        int[] answer = {0, gems.length};
        Set<String> set = new HashSet<>();
        for (String gem : gems) {
            set.add(gem);
        }
        
        int n = set.size();
        
        Map<String, Integer> map = new HashMap<>();
        int s = 0, e = 0;
        
        while (e <= gems.length) {
            if (map.size() < n) {
                int cnt = map.getOrDefault(gems[e], 0) + 1;
                map.put(gems[e], cnt);
                e++;
                
            } else if (map.size() == n) {
                if (answer[1] - answer[0] + 1 > e - s + 1) {
                    answer[0] = s;
                    answer[1] = e;
                }
                
                
                int cnt = map.get(gems[s]);
                
                if (cnt == 1) {
                    if (e == gems.length) break;
                    int v = map.getOrDefault(gems[e], 0) + 1;
                    map.put(gems[e], v);
                    e++;
                    continue;
                }
                
                map.put(gems[s], cnt-1);
                s++;
            }
        }
        
        answer[0]++;
        return answer;
    }
}

 

 

🔅 리팩토링

❗ 오답노트 / 필요한 지식

1. 오랜만에 재밌는 투포인터 문제를 풀었다. 실전에서는 테스트 케이스를 잘 구비해놓자.