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

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

프로그래머스

투 포인터를 사용하는 문제이다.

 

 

핵심

모든 종류의 보석을 갖는 경우를 알아야 하고 만약 모든 보석을 가지고 있다면 1칸씩 당기면서 보석을 버리고, 그때도 모든 종류의 보석을 가지고 있는지 체크하며 최소의 길이를 찾아야 한다.

 

정답 코드

import java.util.Arrays;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Set;

class Solution {
    public int[] solution(String[] gems) {
        Set<String> set = new HashSet<>(Arrays.asList(gems));
        int length = set.size();
        int left = 0;
        int right = 0;
        int dis = Integer.MAX_VALUE;
        int resultLeft = 0;
        int resultRight = 0;
        HashMap<String, Integer> map = new HashMap<>();

        while (true) {
            if (map.size() == length) {
                if (dis > right - left) {
                    dis = right - left;
                    resultLeft = left + 1;
                    resultRight = right;
                }
                map.put(gems[left], map.get(gems[left]) - 1);
                if (map.get(gems[left]) == 0) {
                    map.remove(gems[left]);
                }
                left++;
            } else if (right == gems.length) {
                break;
            } else {
                map.put(gems[right], map.getOrDefault(gems[right], 0) + 1);
                right++;
            }
        }
        return new int[]{resultLeft, resultRight};
    }
}

해설

우선 모든 보석의 갖는 경우를 알기 위해서는 모든 종류의 보석의 개수를 알아야 한다. 

따라서 중복을 무시하는 Set을 사용하여 보석의 종류의 개수를 확인할 수 있다.

Map을 사용하여 현재 보석의 종류별로 가지고 있는 개수를 기록할 수 있다.

중요한 점은 보석의 개수가 0개가 된다면 Map에서 지워야 한다.

이유는 map의 value값이 0 이어도 size를 1칸 차지하기 때문에 map.size == length를 제대로 사용할 수 없기 때문이다.

 

 

배운 점

이 문제를 보자마자 투 포인터라는 사실을 인지하고 풀이법도 바로 떠올랐다. 하지만 정작 while문 내부에서 무한 루프가 돌거나 원하는 답이 나오지 않았다. 머릿속으로는 로직이 떠올랐으나 if문을 rigth 검증부터 하니까 범위에서 논리가 어려워졌다. 이를 left부터 검증하고 다시 논리를 바꾸니 쉽게 풀렸다. 좀 더 논리적인 사고를 해야겠다.