[카카오 인턴] 보석 쇼핑 - Java

문제 내용

어느 날 스트레스를 풀기 위해 보석 매장에 쇼핑을 하러 간 어피치는 이전처럼 진열대의 특정 범위의 보석을 모두 구매하되 특별히 아래 목적을 달성하고 싶었습니다.

진열된 모든 종류의 보석을 적어도 1개 이상 포함하는 가장 짧은 구간을 찾아서 구매

---

조건

가장 짧은 구간의 시작 진열대 번호와 끝 진열대 번호를 차례대로 배열에 담아서 return 하도록 하며,

만약 가장 짧은 구간이 여러 개라면 시작 진열대 번호가 가장 작은 구간을 return 합니다.

gems 배열의 크기는 1 이상 100,000 이하입니다

---

풀이

1. 알고리즘 선택

이 문제를 처음 봤을 땐 dp가 아닐 까? 고민했다.

하지만 배열의 크기가 최대 100,000 이라는 점에서 메모리제이션이 불가능할 것 같아 바로 생각을 접었다.

길이 100,000 이기 때문에 효율성 테스트를 통과하기 위해선 O(n) 또는 O(n logn) 으로 풀어야 한다고 생각했다.

천천히 다시 생각해보니 Set과 Map을 이용하면 투 포인터로 O(n) 으로 풀 수 있을 것 같아 투 포인터로 해결하기로 했다.

---

2. 초기화

먼저 투 포인터를 구현하기에 앞서 등장하는 보석들이 어떤 게 있는지 알아야 했기 떄문에 Gems를 순회하며 allGems에 저장해 주었다.

그리고 left ~ right 포인터 안에 존재하는 보석의 종류를 저장 할 Set (searchGemsSet) ,

left ~ right 포인터 안에 존재하는 보석의 <종류, 갯수> 를 저장할 Map (searchGemsMap) 을 선언하였다.

       HashSet<String> allGems = new HashSet<String>();
        HashSet<String> searchGemsSet = new HashSet<String>();
        HashMap<String,Integer> searchGemsMap = new HashMap<String,Integer>();
        
        for (String gem : gems){
          allGems.add(gem);  
        }
        
        int gemsSize = allGems.size();

3. 투 포인터 구현

투 포인터 구현은 다음과 같은 로직으로 구현했다.

1. 검색한 보석 종류 갯수 < 전체 보석 갯수 인 경우
   • right를 증가
   • 검색한 보석 종류에 추가(Set), 종류별 보석 갯수또한 증가 (Map)
2. 검색한 보석 종류 갯수 = 전체 보석 갯수 인 경우
   • left를 증가
   • 종류별 보석 갯수 감소 (Map)
   • 감소한 보석의 갯수가 0이라면 검색된 보석 종류에서 삭제시켜줌 (Set)

while(left<=right){
          if(searchGemsSet.size() < gemsSize){
              if(right == length) break;
              searchGemsMap.put(gems[right],searchGemsMap.getOrDefault(gems[right],0)+1);
              searchGemsSet.add(gems[right++]);
          }
          if(searchGemsSet.size() == gemsSize){
              if(answerRight - answerLeft > right-1-left){
                  answerRight = right-1;
                  answerLeft = left;
              }
              searchGemsMap.put(gems[left],searchGemsMap.get(gems[left])-1);
              int gemSize = searchGemsMap.get(gems[left]);
              if(gemSize==0){
                  searchGemsSet.remove(gems[left]);
              }
              left++;
          }     
        }

전체 코드

import java.util.*;

class Solution {
    public int[] solution(String[] gems) {
        int[] answer = new int[2];
        int left = 0;
        int right = 0;
        int length = gems.length;
        
        int answerLeft = 0;
        int answerRight = length-1;
        
        HashSet<String> allGems = new HashSet<String>();
        HashSet<String> searchGemsSet = new HashSet<String>();
        HashMap<String,Integer> searchGemsMap = new HashMap<String,Integer>();
        
        for (String gem : gems){
          allGems.add(gem);  
        }
        
        int gemsSize = allGems.size();
        
        
        while(left<=right){
          if(searchGemsSet.size() < gemsSize){
              if(right == length) break;
              searchGemsMap.put(gems[right],searchGemsMap.getOrDefault(gems[right],0)+1);
              searchGemsSet.add(gems[right++]);
          }
          if(searchGemsSet.size() == gemsSize){
              if(answerRight - answerLeft > right-1-left){
                  answerRight = right-1;
                  answerLeft = left;
              }
              searchGemsMap.put(gems[left],searchGemsMap.get(gems[left])-1);
              int gemSize = searchGemsMap.get(gems[left]);
              if(gemSize==0){
                  searchGemsSet.remove(gems[left]);
              }
              left++;
          }     
        }
        answer[0] = answerLeft+1;
        answer[1] = answerRight+1;
        return answer;
    }
}