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

문제 설명

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

문제 풀이

• 투 포인터 알고리즘을 이용하여 풀이하였다.

  L, R을 배열의 인덱스 0으로 두고 다음 로직을 수행한다.

  • R을 0 ~ N-1까지 반복한다.
    - map에 gems[R]을 넣고 값을 1 증가시켜 준다.
    - map에 gems[L]의 값이 1 초과일 때까지 L을 증가시키며 map값을 1줄여줌.
    - 포함하는 보석 수가 전체 종류이고, 구간 길이가 최소일때 최소값 갱신함

소스 코드 (JAVA)

import java.util.*;

class Solution {
    public int[] solution(String[] gems) {
        int kind = new HashSet<>(Arrays.asList(gems)).size();

        Map<String, Integer> map = new HashMap<>();
        int[] result = new int[2];
        int L = 0, min = Integer.MAX_VALUE;
        for (int R = 0; R < gems.length; R++) {
            map.put(gems[R], map.getOrDefault(gems[R], 0) + 1);

            while(map.get(gems[L]) > 1) {
                map.put(gems[L], map.get(gems[L]) - 1);
                L++;
            }

            if (map.size() == kind && min > R - L) {
                min = R - L;
                result[0] = L + 1;
                result[1] = R + 1;
            }
        }
        return result;
    }
}