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

문제

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

코딩테스트 연습 - 보석 쇼핑

 

접근법

처음에는 이중 포문을 사용해서 풀었는데 역시나 시간 초과가 났다.

고민을 오랫동안 했는데도 풀지 못해서

결국 다른 코드를 참고했다.

슬라이딩 윈도우 프로토콜 방식으로 풀어낼 수 있었다.

앞에서 부터 순서대로 보석들을 고르다가 중복된 보석이 나오면 시작 인덱스를 하나씩 밀어주는 방식을 사용했다.

자세한 설명은 코드에 주석을 포함하였다.

 

코드

import java.util.*;

class Solution {
    public int[] solution(String[] gems) {

        Set<String> gemSet = new HashSet<>(); // 보석의 종류를 담은 set
        Map<String, Integer> map = new HashMap<>(); //idx 부터 현재까지의 보석과 그 개수를 저장하는 map
        Queue<String> q = new LinkedList<>(); // idx 부터 현재까지의 보석들을 중복을 포함하여 담은 queue

        //우선 보석의 종류를 파악한다.
        for(String gem : gems){
            gemSet.add(gem);
        }

        int start = 0;
        int idx = 0;
        int min = Integer.MAX_VALUE;
        for(int i=0;i< gems.length;i++){
            //맵에 보석의 개수를 추가해주고
            map.put(gems[i], map.getOrDefault(gems[i], 0)+1);

            //고른 보석을 큐에 넣어준다.
            q.add(gems[i]);

            while(true){
                String temp = q.peek();
                //제일 먼저 고른 보석이 또 나올 경우 제일 먼저 고른 보석을 빼준다.
                //최소를 구해야 하기 때문에 보석이 두개 겹치면 제일 먼저 고른 보석을 빼주어야 최소를 찾을 수 있다.
                if(map.get(temp) > 1){
                    map.put(temp, map.get(temp)-1);
                    //중복된 보석 poll
                    q.poll();
                    //맨 앞에꺼를 빼줬으므로 시작 idx는 +1이 된다.
                    idx++;
                }else{
                    break;
                }
            }

            //앞에 조건은 보석을 모두 고른 경우
            //뒤에 조건은 최소값인 경우 start 인덱스의 값을 갱신신
            if(map.size() == gemSet.size() && min > q.size()){
                min = q.size();
                start = idx;
            }
        }

        return new int[]{start+1, start+min};
    }
}