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

🚨 첫번째 실패 풀이

✔️ 2중 for문

• 보석 종류 수 세기 위해서 Set에 넣고 크기 구하기
• 보석 첫번째 부터 2중 for문 돌면서 새로운 set에 넣고 현재 확인 중인 set 크기랑 보석 종류 수 같고, 구간이 짧으면 answer 배열에 넣기
• 😓 뭐야 쉽네???? 했지만 효율성에서 실패
  

import java.util.*;

class Solution {
    public int[] solution(String[] gems) {
        Set<String> set = new HashSet<>();
        for(String gem : gems){
            set.add(gem);
        }
        
        int[] answer = new int[2];
        int result = Integer.MAX_VALUE;
        for(int i = 0; i<gems.length; i++){
            Set<String> s = new HashSet<>();
            for(int j = i; j<gems.length; j++){
                s.add(gems[j]);

                if(set.size() == s.size()) {
                    if (result > j - i) {
                        result = j - i;
                        answer[0] = i + 1;
                        answer[1] = j + 1;
                    }
                    break;
                }
            } 
        }
        
        
        return answer;
    }
}

🚨 두번째 실패 풀이

✔️ 투포인터 + HashSet

• 이중탐색으로 생각해봤지만 아무리 생각해도 모르겠어서 GPT 한테 힌트를 구하니까 (까먹고 있었던) 투포인터를 사용하라고 했다..!
• 투포인터를 사용하는데 계속 left = 0, right = 배열 사이즈 로 생각 하니까 잘 안풀렸는데 left = 0, right = 0 으로도 풀 수 있었음
• 😓 하지만 while문 안에 또 for문으로 효율성 실패
  

import java.util.*;

class Solution {
    public int[] solution(String[] gems) {
        Set<String> set = new HashSet<>(Arrays.asList(gems));
        int targetCnt = set.size();
        
        int left = 0, right = 0;
        int[] answer = new int[2];
        int cnt = Integer.MAX_VALUE;
        while(left <= right && right < gems.length){
            Set<String> check = new HashSet<>();
            for(int i = left; i<=right; i++){
                check.add(gems[i]);
            }
            
            if (check.size() < targetCnt) right++;
            else if (check.size() == targetCnt) {
                if(cnt > right - left){
                    answer[0] = left+1;
                    answer[1] = right+1;

                    cnt = right - left;
                }

                left++;
                       
            }
        }
        
        
        return answer;
    }
}

💡 정답 풀이

✔️ 투포인터 + HashMap

• 데이터를 1번만 순회해야 효율성에 통과해야하는 데 떠오르지 않아서 다른 사람 풀이 참고 ..
• 보석을 하나씩 추가하는데 해시맵에 저장해서 몇개가 들어있는지 Count => 다음에 right +1
• 해시맵에 보석 종류가 다 들어온 경우 (= 해시맵 사이즈가 종류 수랑 같은 경우)
  => 짧은 구간 찾아서 answer 배열 갱신
  => 더 짧은 구간 있는지 파악하기 위해 left 증가, 이때 증가하기전에 해시맵에서 left 지점에 있는 보석 수 빼기

import java.util.*;

class Solution {
    public int[] solution(String[] gems) {
        Set<String> set = new HashSet<>(Arrays.asList(gems));
        int types = set.size();
        
        int left = 0, right = 0;
        int[] answer = new int[2];
        int minLen = Integer.MAX_VALUE;
        
        HashMap<String, Integer> gem = new HashMap<>();
        while(right < gems.length){
            // 보석 추가
            gem.put(gems[right], gem.getOrDefault(gems[right], 0) + 1);
            right++;
            
            // gem 해시맵에 보석이 다 들어온 경우
            while (gem.size() == types) {
                // 보석 중 짧은 구간 찾기
                if (minLen > right - left){
                    answer[0] = left+1;
                    answer[1] = right;

                    minLen = right - left;
                }
                
                // left 위치 늘리고 기존 left는 gem 해시맵에서 제거
                gem.put(gems[left], gem.get(gems[left]) - 1);
                if (gem.get(gems[left]) == 0){
                    gem.remove(gems[left]);
                }
                left++;
                       
            }
        }
        
        
        return answer;
    }
}