문제 링크
https://school.programmers.co.kr/learn/courses/30/lessons/67258
문제 설명
개발자 출신으로 세계 최고의 갑부가 된 어피치는 스트레스를 받을 때면 이를 풀기 위해 오프라인 매장에 쇼핑을 하러 가곤 합니다.
어피치는 쇼핑을 할 때면 매장 진열대의 특정 범위의 물건들을 모두 싹쓸이 구매하는 습관이 있습니다.
어느 날 스트레스를 풀기 위해 보석 매장에 쇼핑을 하러 간 어피치는 이전처럼 진열대의 특정 범위의 보석을 모두 구매하되 특별히 아래 목적을 달성하고 싶었습니다.
진열된 모든 종류의 보석을 적어도 1개 이상 포함하는 가장 짧은 구간을 찾아서 구매
예를 들어 아래 진열대는 4종류의 보석(RUBY, DIA, EMERALD, SAPPHIRE) 8개가 진열된 예시입니다.
진열대의 3번부터 7번까지 5개의 보석을 구매하면 모든 종류의 보석을 적어도 하나 이상씩 포함하게 됩니다.
진열대의 3, 4, 6, 7번의 보석만 구매하는 것은 중간에 특정 구간(5번)이 빠지게 되므로 어피치의 쇼핑 습관에 맞지 않습니다.
진열대 번호 순서대로 보석들의 이름이 저장된 배열 gems가 매개변수로 주어집니다. 이때 모든 보석을 하나 이상 포함하는 가장 짧은 구간을 찾아서 return 하도록 solution 함수를 완성해주세요.
가장 짧은 구간의 시작 진열대 번호와 끝 진열대 번호를 차례대로 배열에 담아서 return 하도록 하며, 만약 가장 짧은 구간이 여러 개라면 시작 진열대 번호가 가장 작은 구간을 return 합니다.
제한사항
알고리즘: 투 포인터
풀이
gems 배열의 크기는 최대 100,000이다. 그렇기 때문에 O(N) 풀이나 O(N * logN)풀이가 가능한데, 시간 복잡도 O(N)인 투 포인터 알고리즘이 이 문제에 적합하다.
먼저 나는
보석의 종류를 세기 위한 HashMap, 각 보석 개수를 세기 위한 HashMap , 검사해 줄 보석의 인덱스를 담은 Queue를 선언했다.
gems 배열을 순차 탐색하면서 Queue와 HashMap(보석 개수를 세기 위한)에 보석을 담아준다. (순차 탐색하는 과정이 투 포인터에서는 뒤쪽 포인터를 이동시키는 과정임)
모든 보석의 종류를 담았을 때 앞쪽 포인터를 이동시키면서 최적의 구간을 구해야 한다.
최적의 구간은 어떤 구간이냐? 당연히 모든 보석을 가지고 있으면서 짧아야 하는 구간이다.
while(jew.get(gems[que.peek()]) > 1) {
int ind = que.poll();
jew.put(gems[ind], jew.get(gems[ind]) - 1);
}위 코드가 앞쪽 포인터를 이동시키면서 최적의 구간을 구하는 코드이다.
이런 식으로 순차탐색이 끝날 때까지(뒤쪽 포인터가 끝에 도달할 때까지) 반복해주면 된다.
투 포인터의 시간 복잡도가 O(N)인 이유를 보면 앞쪽 포인터와 뒤쪽 포인터 각각의 최대 누적 횟수는 N이기 때문이다.
소스 코드
import java.util.*;
class Solution {
static HashMap<String, Boolean> jew_types = new HashMap<>();
static HashMap<String, Integer> jew = new HashMap<>();
static Queue<Integer> que = new LinkedList<>();
public int[] solution(String[] gems) {
int[] answer = {1, Integer.MAX_VALUE};
for(int i=0; i<gems.length; i++) if(jew_types.get(gems[i]) == null) jew_types.put(gems[i], true);
for(int i=0; i<gems.length; i++) {
if(jew.get(gems[i]) == null) jew.put(gems[i], 1);
else jew.put(gems[i], jew.get(gems[i]) + 1);
que.add(i);
if(jew.size() == jew_types.size()) {
//모든 보석 종류가 모였다면
while(jew.get(gems[que.peek()]) > 1) {
int ind = que.poll();
jew.put(gems[ind], jew.get(gems[ind]) - 1);
}
if(answer[1] - answer[0] > i - que.peek()) {
answer[0] = que.peek() + 1;
answer[1] = i + 1;
}
}
}
return answer;
}
}