[프로그래머스/Level3] 보석 쇼핑 (JAVA)

📖 문제

프로그래머스

 

 

 

💡  풀이 방식

• 투 포인터  ▷ 탐색 대상 : 모든 보석 구매하기 위한 최소 구간

 

필요 자료구조
- 보석 "종류" 저장용 Set
- 보석 "구간" 저장용 Set
- <보석 종류, 구간 별 보석 수> 저장용 Map

투 포인터 구간 탐색 위한 int형 변수 - left와 right (초기값 : 모두 0)

 

1. map에 right쪽에 위치한 보석을 넣는다.

2. left에 위치한 보석이 중복이라면, 보석 갯수를 줄이고, 시작 구간을 1 증가한다.

3. 모든 보석을 탐색했으며 (set1.size() == set2.size()), 최단 구간이라면 최단 구간을 갱신한다.

 

 

💥 유의사항

크기가 10만이라 시간 복잡도에 유의해야 한다.

 

 

🔺 코드

import java.util.*;
 
class Solution {
    public int[] solution(String[] gems) {
        
        Set<String> set1 = new HashSet<>(); // 보석 "종류" 저장
        Set<String> set2 = new HashSet<>(); // 보석 "구간 저장
        Map<String, Integer> map = new HashMap<>(); // 보석 종류, 구간 별 보석 수
        
        // 보석 수 구할 목적
        for(String g : gems) {
            set1.add(g);
        }
        
        int left = 0;
        int right = 0;
        int len = Integer.MAX_VALUE;
        
        int[] answer = new int[2];
                
        while(right < gems.length) {            
            map.put(gems[right], map.getOrDefault(gems[right], 0) + 1); // 보석 추가
            set2.add(gems[right]);
            
            // 해당 구간의 보석이 2개 이상인 경우, 제거하고 다음 구간으로 이동해 탐색 범위 넓히기
            while(map.get(gems[left]) > 1) {
                map.replace(gems[left], map.get(gems[left]) -1);
                left++;
            }
            
            // 모든 보석 종류를 모았고, 이전에 구한 구간보다 길이가 짧은 경우
            if(set1.size() == set2.size() && right - left < len) {
                answer[0] = left + 1;
                answer[1] = right + 1;
                len = right - left;
            }
            right++;    // 오른쪽으로 한 칸 확장하기
        }
                
        return answer;
    }
}

 

 

 

 

➕ 다른 풀이 방식

- end 인덱스 이동시킬 때 for문 사용하셨고, Set 1개로 처리한 풀이. set의 크기를 저장하는 int형 변수를 만들어서 map의 크기가 같고, 구간 길이가 최소 길이라면, 이 값으로 갱신하다.   (추구미,,,📌)

[프로그래머스,Java] Level3: 보석 쇼핑

 

 

- Set, Map, Queue를 모두 활용한 풀이 (set2를 사용하는 대신 큐 만들어 사용 - 연속선택이므로)

보석 쇼핑 - 카카오 인턴십 2020 프로그래머스 LV3 JAVA

프로그래머스 - 보석 쇼핑 문제 (자바)

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

---

💦 어려웠던 점

- 투 포인터 left를 0번째로, right를 맨 뒤 원소로 하려다가 둘다 0으로 설정해야한다는 것을 꽤 오랜 시간 후 눈치챘다...

- 필요한 변수와 과정을 먼저 정리하고 시작하자... 안 그러면 확신도 안 서고 머릿속에서 꼬인다..

 

1회독	2회독	3회독	4회독	5회독
V

 

---

(참고)

[프로그래머스 / Level3] 보석 쇼핑 (Java)