문제

보석 쇼핑

풀이

이때 모든 보석을 하나 이상 포함하는 가장 짧은 구간의 길이를 찾는 문제이다.
투포인터 알고리즘을 사용해야 한다..

1. 보석 종류를 담을 수 있는 자료형 선언

		// 시작위치, 증가 구간 넓이, 현재 구간 넓이
        int start = 0, count = 0, interval = Integer.MAX_VALUE;
		HashSet<String> set = new HashSet<>(); // 보석의 종류 개수
        HashMap<String, Integer> map = new HashMap<>(); // 보석 종류당 보석 등장 개수
        Queue<String> q = new LinkedList<>(); // 구간안의 보석

2. 현재위치의 보석을 큐에 넣어주고 가장 앞에 있는 보석이 2개이상 들어오게 되고 보석의 종류가 전부 큐안에 들어오면 넓어져야 하는 위치를 갱신해준다.

		for (int i = 0; i < gems.length; i++) {
            map.put(gems[i], map.getOrDefault(gems[i], 0) + 1);
            q.add(gems[i]);

            while (map.get(q.peek()) > 1) {
                map.put(q.peek(), map.get(q.poll()) - 1);
                count++;
            }

            if (map.size() == set.size() && interval > i - count) {
                interval = i - count;
                start = count + 1;
            }
        }

문제를 보고 어떻게 투포인터를 바로생각해내야 하는걸까

전체 코드

전체 코드