출처: https://programmers.co.kr/learn/courses/30/lessons/67258
[1.이해]
예시
보석 배열: [3,1,2,1,2,0,1,0,3]
종류: [0,1,2,3]
종류를 다 포함하는 가장 짧은 수열: [2,0,1,0,3]
모든종류가 다 들어왔는 지 확인하기 위해서 배열을 탐색하면서 보석을 컨테이너에 집어넣고 컨테이너의 사이즈=종류의 수 인지 비교하면 된다. 이때 컨테이너의 사이즈 뿐만 아니라 수열의 길이에 대해서 검사하기 위해서 컨테이너에는 보석의 종류 뿐만 아니라 값의 보석의 위치도 포함 되어야한다.
[2.알고리즘 선택]
먼저 보석의 종류와 위치정보에 대해서 가지고 탐색을 해 나가야한다.
이 문제를 푸는데 떠올린 생각은 2가지다.
1. 이분탐색
보석 담을 컨테이너: 순서가 정렬되어있는 Vector(다이나믹 어레이)
알고리즘 순서
- 보석을 넣을때마다 순서에 맞게 삽입한다.
- 이때 컨테이너에 이미있던 종류의 보석에 대해서 들어올 경우 위치를 바꿔치기 한다.
- 이때 바꿔치기에 의해서 시작지점이 변경된다면 이를 갱신한다.
- 길이(끝지점-시작지점)를 이전 최저길이와 비교한다.
시간복잡도
- 하나의 데이터 삽입경우
(1)삽입 부분 탐색시간: O(logN)
(2)갱신 시간: O(N)의 복잡도를 보이게 된다.
갱신 시간을 줄이기 위해서 우선순위큐를 쓰는방법도 고려 하였지만 보석의 위치들이 바꿔치기할 때마다 우선순위큐의 데이터도 변동을 시켜줘야 하는데 더 복잡해진다.- 전체 데이터 삽입시
최악으로N*((logN+N))다음이 발생할 수 있다.결론
사실상 브루트 포스방식의 탐색으로 생기는 시간복잡도 O(N^2)비교했을때 큰 장점이 없다.
2. 큐방식
1.컨테이너
- 보석의 종류만 담겨있는 queue.
- Queue에 같은 보석이 몇개나 들어왔는지 확인하기 위한 map<종류,수> kindsMap
2.순서
[1].탐색시 보석종류를 queue에 push하고 KindsMap[보석종류]+1한다.
[2].queue의 front에 해당하는 보석종류의 갯수가 여러개일 경우 queue.pop()한다.
pop하게 되면 [3]으로 넘어가고 그렇지 않다면 [4]로 넘어간다.
[3].pop을 된다면 시작지점을 +1하고 kindsMap[보석종류]-1한다.
[4].queue안에 모든 사이즈의 보석이 있다면( kindsMap사이즈를 가지고 판단) 현재까지의 최소 수열길이와 비교하고 갱신한다.시간복잡도
- queue를 사용하면 O(N)이 보장가능하다.
결론
이분탐색방식과 비교했을때 사용하기 간단하면서 훨씬 효율적이다.
[4.구현]
#include <bits/stdc++.h>
using namespace std;
unordered_map<string, int> GemsMap; // key:보석이름 value:정수로 변환된 보석종류
vector<int> GemsVec;
unordered_map<int, int> KindsCount; //key=보석종류,value=수
queue<int> Gemque;
int start_ = 0, end_ = 0, tempStart = 0, tempEnd = 0;
int Kinds = 0;
int MinLength = 2e9;
vector<int> solution(vector<string> gems)
{
for (auto &gem : gems)
{
if (GemsMap[gem] == 0)
{
++Kinds;
GemsMap[gem] = Kinds;
}
GemsVec.push_back(GemsMap[gem]);
}
for (auto gem : GemsVec)
{
Gemque.push(gem); //1
KindsCount[gem]++; //1
while (KindsCount[Gemque.front()] > 1) //2~3
{
KindsCount[Gemque.front()]--;
tempStart++;
Gemque.pop();
}
if ((int)KindsCount.size() == Kinds && (int)Gemque.size() < MinLength) //4
{
MinLength = Gemque.size();
start_ = tempStart;
end_ = tempEnd;
}
tempEnd++;
}
return vector<int>({start_ + 1, end_ + 1});
};
[5.고찰]
Queue로 푸는데 익숙해지자.
