프로그래머스 - 보석 쇼핑

보석 쇼핑 : https://programmers.co.kr/learn/courses/30/lessons/67258

---

Problems

---

Solves

투 포인터 알고리즘을 이용한 문제라고 한다.

여기서 투 포인터란 배열을 탐색할 때 쉽고 효율적인 방법으로 사용하기 위한 방법이다.
하나의 배열이 있고 두 개의 포인터를 start, end로 지칭했을때 각각 시작점과 끝점으로 놓고 조건에 맞게 start와 end를 이동하면서 배열 전체를 탐색하는 것이다.(start, end이 배열의 시작점인 경우와 각각 시작점과 끝점으로 놓고 하는 방법이 있다)
투 포인터를 사용하지 않았을 경우 이중 for문을 사용해서 O(N^2)가 되지만, 투 포인터를 사용하면 O(N)으로 선형 탐색이 가능하게 된다.
(투 포인터 문제 : https://www.acmicpc.net/problem/2003)

다시 문제로 돌아와서 보석 진열을 나타내는 배열인 gems를 돌면서 최소한의 보석 진열의 범위를 가지면서 모든 보석 종류를 포함하는 start와 end를 찾는 문제이다.

문제 풀이 순서는 다음과 같다.

1. 보석 종류를 저장하는 HashSet gemSet
2. 탐색한 진열 범위에서 존재하는 보석 종류 별 갯수 HashMap<String, Integer> gemMap
3. 탐색한 진열 범위의 보석 저장 Queue gemQueue
4. gems를 탐색하면서 gemMap에 해당 위치에 있는 보석을 gemMap에 갯수를 추가해주고, gemQueue에 보석을 추가한다.
5. 탐색한 범위의 보석들 중 맨 앞의 보석의 갯수가 2개 이상을 가질 경우 1개가 될때까지 반복한다.
   (탐색한 범위에서 맨 앞에 보석이 있고 그 뒤에도 보석이 있다면 맨 앞의 보석을 제거해서 start의 범위를 줄여주기 위함이다.)
6. 보석 종류의 갯수(gemSet)과 탐색 범위의 보석 종류(gemMap)의 크기가 같다면 해당 범위(start, end)를 갱신해준다.
   이때 기존의 범위가 해당 범위보다 작거나 같다면 갱신해주지 않는다.(범위가 동일하다면 시작 진열대 번호가 가장 작은 번호 범위를 반환해야하기 때문이다.)

문제의 테스트케이스 디버깅

---

Code

import java.util.HashMap;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.Queue;
class Solution {
    public int[] solution(String[] gems) {
  		//보석 종류 저장
        HashSet<String> gemSet = new HashSet<>();
  		//탐색 범위 보석 종류의 갯수 저장
        HashMap<String,Integer> gemMap = new HashMap<>();
  		//탐색 범위 보석 저장
        Queue<String> gemQueue = new LinkedList<>();
        
        for(String gem : gems){
            gemSet.add(gem);
        }
        
  		//최소 범위의 시작점
        int start=0;
  		//최소 범위의 끝점
        int end=gems.length-1;
  		//범위 계산시 사용될 임의 시작점
        int startPoint = 0;
  		//최소 범위
        int distance = end-start;
        for(int g = 0;g<gems.length;g++){
			//탐색할 범위에 보석의 갯수와 보석을 저장해준다.
            gemMap.put(gems[g], gemMap.getOrDefault(gems[g],0)+1);
            gemQueue.offer(gems[g]);
            while(true){
				//탐색한 범위의 맨 앞 보석의 갯수가 1개가 될때까지 반복
                if(gemMap.get(gemQueue.peek()) > 1){
  					//해당 보석의 갯수를 줄여주고
                    gemMap.put(gemQueue.peek(), gemMap.get(gemQueue.peek())-1);
                    //탐색한 범위의 맨 앞 보석을 지워줌
  					gemQueue.poll();
  					//탐색의 범위가 줄어듬
                    startPoint++;
                }else{
                    break;
                }
            }
            
  			//해당 범위 안의 보석 종류의 갯수와 총 보석 종류의 갯수가 같고
  			//기존 탐색 범위보다 해당 탐색 범위가 더 작다면 최소 범위 갱신.
            if(gemMap.size() == gemSet.size() && distance>gemQueue.size()){
                distance = gemQueue.size();
                start = startPoint;
                end = g;
            }
        }

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

---

Result

gems의 길이가 100000이고 gems가 {DIA, RUBY, RUBY, ... , RUBY, DIA, EMERALD} 인 경우 gems를 돌때 while문에서 RUBY의 중복을 제거해줄때 거의 O(100000 * 100000)에 가까운 시간복잡도가 발생해서 시간초과가 발생하지 않나 라는 생각을 했다.
질문하기에 올려놨으니.. 내가 잘못이해하고 있다면 지적이라도 해줬으면 좋겠다..

---

Reference

https://asong-study-record.tistory.com/77