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

문제링크

[문제 설명]

1. 진열대 번호 순서대로 보석이 담겨 있다.
2. 진열된 모든 종류의 보석을 적어도 1개 이상 포함하는 가장 짧은 구간을 찾아낸다.
3. 만약 가장 짧은 구간이 2가지 이상이라면 시작 인덱스가 짧은 곳을 출력한다.

Two Pointer로 접근

public class Solution {
    private final Set<String> set = new HashSet<>();
    private final Map<String, Integer> map = new HashMap<>();
    private static int MIN_LENGTH;
    private static int MIN_START_INDEX;


    public int[] solution(String[] gems) {
        int[] answer = new int[2];
		
        // 1. 모든 보석의 종류를 담을 Set을 선언한다.
        for (String gem : gems) {
            if (!set.contains(gem)) {
                set.add(gem);
            }
        }

        int start = 0;	/* 투 포인터를 위한 start index */
        int end = 0;	/* 투 포인터를 위한 end index */

        int nowLength;
        MIN_LENGTH = gems.length;
        MIN_START_INDEX = gems.length;
		
        //2. 만약 Set 사이즈가 1일 경우 {1,1}을 반환
        if (set.size() == 1) {
            return new int[]{1, 1};
        }
		
        //two pointer 탐색 구간
        while (start < gems.length) {
            nowLength = end - start + 1;
            if (nowLength > MIN_LENGTH || end == gems.length) {
                removeElement(gems[start]);
                start++;
            } else {
                addElement(gems[end]);
                end++;
            }
            // 모든 보석이 포함되어 있을 경우
            if (containAllJewerlys()) {
                getMinLength(start, end);
                getMinIndex(start, nowLength);
            }
        }

        answer[0] = MIN_START_INDEX + 1;
        answer[1] = answer[0] + MIN_LENGTH - 1;

        return answer;
    }

	private boolean containAllJewerlys() {
    	return map.size() == set.size();
    }

    private void getMinLength(int start, int end) {
        if (end - start < MIN_LENGTH) {
            MIN_LENGTH = end - start; // 막혔던 부분
            MIN_START_INDEX = start;
        }
    }

    private void getMinIndex(int start, int nowLength) {
        if (nowLength == MIN_LENGTH) {
            if (MIN_START_INDEX > start) {
                MIN_START_INDEX = start;
            }
        }
    }

    void removeElement(String element) {
        if (map.get(element) == 1) {//막혔던 부분
            map.remove(element);
        } else {
            map.put(element, map.get(element) - 1);
        }
    }

    void addElement(String element) {
        if (!map.containsKey(element)) {
            map.put(element, 1);
        } else {
            map.put(element, map.get(element) + 1);
        }
    }
}

코드 설명

1. 모든 보석 내용을 담고 있는 Set을 선언한다.
2. 보석과 보석의 갯수를 확인할 수 있는 Map을 선언한다.
3. start, end pointer를 이용해서 탐색한다.
   • 모든 보석이 들어있지 않을 경우
     → map에 보석과 갯수 추가 + end index++
   • 모든 보석이 들어가 있지만 현재 길이가 최소 갯수를 초과하는 경우,
     → map의 보석 갯수 제거 + start index++;
     

4. map에서 모든 보석을 가지고 있는 경우,
→ 조건 확인 후, 최소 길이 및 최소 시작 인덱스 갱신

😁Reference

• 투포인터 설명 및 관련 문제

💪To Do List

• 투포인터 설명 및 문제 링크 연습하기