카카오코테 - 보석쇼핑

코드

import java.util.*;

class Solution {
    public int[] solution(String[] gems) {
       int[] answer = new int[2];
        Set<String> set = new HashSet<>(Arrays.asList(gems));
        Map<String, Integer> map = new HashMap<>();

        int distance = Integer.MAX_VALUE;
        int start = 0;

        for (int i = 0; i < gems.length; i++) {
            map.put(gems[i], map.getOrDefault(gems[i], 0) + 1);
            
            if (map.size() != set.size())
                continue;

            while (map.size() == set.size()) {
                map.put(gems[start], map.get(gems[start]) - 1);
                if (map.get(gems[start]) == 0) {
                    map.remove(gems[start]);
                }
                start++;
            }

            if (i - start < distance) {
                answer[0] = start;
                answer[1] = i + 1;
                distance = i - start;
            }
            
        }
        return answer;
    }
}

풀이

🤔문제를 보자마자 투 포인터라는 것은 알았으나 구현에 있어 생각보다 복잡해서 시간이 걸린 문제입니다.(기존의 투 포인터 방식이라기보다는 start(시작 부분) 변수를 조금 더 활용하여 푼 방식입니다.)

1. 총 보석의 개수를 구해줍니다. set을 이용하여 구하였습니다.
2. map을 선언합니다. map에는 해당 보석의 개수를 넣어줄 것입니다.
3. distance, start 는 각각 거리와 구간을 구하기 위한 변수입니다.
4. gems를 기준으로 for문을 돌려줍니다. 먼저 해당 gem을 map에 넣어주는데 이 때 map에 이미 있다면 1을 더해주면 됩니다.
5. map의 key값의 개수가 보석의 총 합과 다르다면 continue를 진행해주시면 됩니다. 같을 경우 while문으로 start를 1씩 올려줍니다.
   현재 상황은 이미 모든 보석이 존재하고 있는 상태인데 여기서 start를 하나씩 올렸는데 만약 모든 보석이 존재하지 않는다면 전 값을 넣어주면 되고 모든 보석이 존재할 경우에는 계속 start를 하나씩 올려주면 됩니다. 이 과정을 거치면 최소값을(해당 구간에서의) 찾을 수 있습니다.
6. distance보다 작을 경우에는 정답값과 distance를 갱신해줍니다.

😭처음에는 투 포인터 방식처럼 start, end로 풀려고 하였으나 여러 변수를 선언하다 보니 복잡해져서 다른 분들의 풀이 방식을 참고하여 보니 map.size()라는 것을 알게 되어 이를 적용해보니 전보다 더 좋은 방식으로 풀렸습니다. 생각보다 어렵네요...

출처 : 프로그래머스 - 보석 쇼핑