처음 문제를 봤을 때 set이나 map을 사용해야 될 것 같긴 했는데 전반적인 풀이 방법이 떠오르지 않아 다른 사람 코드를 참고했습니다. 효율성을 따진다는 것 + 보석의 개수가 최대 10만 개라는 점에서 모든 경우를 다 탐색한다는 것은 시간 초과가 날 것이라 생각했고, 풀이를 보니 투 포인터를 사용하는 것이었습니다.
투 포인터 문제를 많이 풀어보지는 않았지만 보석 쇼핑과 같이 연속되는 데이터를 찾는 문제(?) 유형에 많이 사용되는 것 같습니다.
풀이 방법
- map에 보석의 종류와 개수를 담아줍니다.
- 보석의 종류를 중복 없이 담기 위해서 set을 사용합니다. 아래와 같이 set을 선언하면 gems vector의 처음부터 끝까지 중복되지 않게 데이터를 set에 담아줍니다.
- 보석의 종류를 다 포함하는 최소의 end 위치를 구합니다. 입출력 예의 1번으로 치면 "DIA[인덱스 0번]부터 SAPPHIRE[인덱스 6번] 까지를 의미 합니다. map에 보석이 다 담기게 되면 map의 size는 set의 size와 같게 됩니다. 그 상태의 i를 end로 지정합니다.
- 구해진 end에서 start를 빼서 minDist 변수를 초기화합니다.
- 투 포인터를 진행할 때 start의 위치를 오른쪽으로(end 쪽으로) 한 칸씩 이동하면서 최소의 길이를 구하게 되는데 이때 start가 움직여도 map의 size는 여전히 전체 보석의 개수(set의 size)와 같아야 합니다. start가 이동하면 원래 start 위치에 있던 보석의 개수가 하나 줄어드는데 개수가 한 개 줄어듦으로써 map의 size가 set의 size와 달라진다면 end를 오른쪽으로 이동합니다. 코드에서는 map의 value 값이 0이라면 보석이 하나도 없는 것을 의미합니다.
- end가 오른쪽으로 이동하더라도 gems vector의 size 이상으로는 움직일 수 없기 때문에 while문의 조건을 end < gems.size()로 지정했습니다.
- map의 size가 다시 set의 size와 같아질 때까지 end를 오른쪽으로 움직이면서 end 위치의 보석을 map에 담아줍니다.
- end-start가 기존의 minDist보다 작다면 end와 start를 다시 answer 변수에 대입합니다.
#include <string>
#include <vector>
#include <map>
#include <set>
using namespace std;
vector<int> solution(vector<string> gems) {
map<string, int> zmaps;
vector<int> answer;
set<string> zsets(gems.begin(), gems.end());
int zsets_size = zsets.size();
int start =0, end = gems.size()-1;
// 보석을 다 포함하는 end를 구함
for(int i=0;i<gems.size();i++){
zmaps[gems[i]]++;
if(zsets_size == zmaps.size()){
end = i;
break;
}
}
answer = {start+1, end+1};
int minDist = end - start;
while(end < gems.size()){
string gem = gems[start];
zmaps[gem]--;
start++;
if(zmaps[gem] == 0){
end++;
while(end < gems.size()){
zmaps[gems[end]]++;
if(gems[end] == gem){
break;
}
end++;
}
}
if(end-start < minDist){
answer = {start+1, end+1};
minDist = end-start;
}
}
return answer;
}