프로그래머스 - 보석 쇼핑

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

프로그래머스

 

 

 

 

 

문제

진열대 번호	1	2	3	4	5	6	7	8
보석 이름	DIA	RUBY	RUBY	DIA	DIA	EMERAID	SAPPAIRE	DIA

• 모든 범위의 보석 1개이상 포함하는 짧은 구간(시작점, 끝점) 구하기
  • 여러 개라면 시작 작은 구간

 

제한사항

• 배열 크기 : 1 이상 100,000 이하

 

 

 

 

 

풀이

배열의 크기가 최대 10만으로 O(N^2)으로 푼다면 시간초과가 날 것이다. 가장 짧은 구간을 구하는 문제로 투포인터를 사용하여 푼다면 O(N^2)미만으로 풀이가 가능하다.

 

 

 

• HashSet으로 진열대에 있는 보석의 종류의 수 구하기

 모든 보석을 포함하는 구간을 구해야 하므로, 우선 보석의 종류가 총 몇 가지인지 알아야 한다. 보석 배열을 순회하며 중복을 제거하는 자료구조인 HashSet에 보석을 담으면, 보석의 종류 개수를 알 수 있다.

 

 

 

• HashMap에 보석별 개수 저장

 모든 종류의 보석이 있는지 확인하려면, 구간 안에 어떤 보석이 몇 개있는지 알아야 한다. 보석별로 개수를 저장하기 위해 HashMap<string, integer>에 보석과 개수를 저장한다.

 

 

 

• 투포인터

 투포인터를 풀 때, 포인터를 모두 시작점에 두고 시작하거나, 포인터를 양 끝에 두고 시작할 수 있다. 정해진 연속된 범위를 탐색해야 하므로, 포인터를 모두 시작점에 두고 탐색을 시작하면 된다.

 

 

1. right 포인터를 하나씩 늘려가며 탐색한다. 그리고 right에 해당하는 보석 개수를 증가시킨다.

2. left에 해당하는 보석이 1개를 초과할 때까지, 해당 종류의 보석의 개수를 차감시키고, left 포인터로 증가시킨다.

3. left 포인터 조작이 끝나고, map의 사이즈(현재 구간 안 보석 종류 수)가 set의 사이즈(보석의 종류 수)와 같고, 가장 짧은 구간이면, 값을 갱신한다.

 

 

 

 

 

코드

import java.util.*;

class Solution {
    public int[] solution(String[] gems) {
        HashSet<String> set = new HashSet<>(); //보석의 종류
        for(String gem : gems) {
            set.add(gem);
        }
        
        int left = 0;
        int target = set.size(); //모든 보석 개수
        int min = 100000; //가장 짧은 구간
        int[] answer = new int[2]; //시작번호, 끝번호
        
        HashMap<String, Integer> map = new HashMap<>(); //보석, 개수
        
        for(int right = 0; right < gems.length; right++) { //right 포인터 끝까지 탐색
            map.put(gems[right], map.getOrDefault(gems[right], 0) + 1); //right 해당 보석 개수 증가
            
            while(map.getOrDefault(gems[left], 0) > 1) { //left 해당 보석이 1개 초과할때까지 포인터 증가
                map.put(gems[left], map.get(gems[left]) - 1); //해당 보석 개수 감소
                left++;
            }
            
            if (map.size() == target && right - left < min) { //모든 보석 포함 & 가장 짧은 구간 발견
                min = right - left;
                answer[0] = left + 1;
                answer[1] = right + 1;
            }
        }
        
        return answer;
    }
}

 

 

 

 

 

결과

 

 

 

 

 

배운점