(출처) https://programmers.co.kr/learn/courses/30/lessons/67258
특정조건의 정답구간 구하기
최대길이가 100,000을 넘지 않는 gems 배열이 입력으로 주어질 때, 해당 배열 내에서 "모든 종류의 보석을 적어도 1개 이상 포함하는 가장 짧은 구간을 찾아 리턴"해야 되는 문제이다.
또한 문제에는 보석의 구매자가 특정 범위의 보석들을 모두 싹쓸이해서 구매하는 습관이 있다는 조건이 붙어있다.
구매자가 특정 범위의 보석을 모두 싹쓸이한다는 조건은, 정답으로 리턴해야 하는 범위구간이 부분부분 띄워져있는 여러 개의 구간으로 구성되는 것이 아니라 연속된 하나의 구간이 된다는 것을 뜻한다.
정답 구간이 하나의 연속된 구간이라는 조건에서부터 투포인터를 이용하여 문제를 풀면 될 것 같다는 느낌을 느꼈다.
2개의 가상 포인터를 주어진 배열의 0번 인덱스에 위치 시켜놓고 포인터를 하나씩 움직여가며 구간을 조절하는 식으로 탐색을 진행하며 접근하면 될 것 같았다.
정답구간이 갱신되는 지점
투포인터에서 오른쪽 포인터가 증가하면 전체 구간은 증가하고, 왼쪽 포인터가 증가하면 전체 구간은 감소한다.
우선은 오른쪽 포인터 인덱스를 한 칸씩 증가시키면서 배열을 탐색하고 문제의 정답이 될 수 있는 구간(오른쪽 포인터를 고정시킬 구간)을 찾아야 한다.
해당 문제에서는 정답구간은 반드시 모든 종류의 보석을 1개씩 포함하고 있어야 한다는 조건이 존재한다.
문제의 이 조건을 한 번 곰곰이 생각해 본다면, 오른쪽 포인터가 움직이면서 새롭게 발견한 보석이 지금까지 단 한 번도 발견되지 않았던 종류의 보석일 때 무조건 정답이 새롭게 갱신됨을 뜻한다는 것을 알 수 있다.
즉 배열에서 새로운 종류의 보석을 발견할 때마다 현재 오른쪽 포인터가 가리키고 있는 위치가 리턴해야 할 새로운 정답구간의 답으로 갱신되어 고정된다.
이렇게 배열의 끝까지 원소를 탐색해서 오른쪽 포인터를 알맞게 고정시켜 놨다면 이제 왼쪽 포인터의 위치를 고정시키는 것은 딱히 어려울 것이 없다.
현재 투포인터가 가리키고 있는 구간 내에서 왼쪽포인터가 가리키고 있는 보석이 몇 개나 존재하는지 카운팅 해주면 된다.
만약 왼쪽포인터가 가리키고 있는 보석 종류가 이미 구간에 2개 이상으로 존재하고 있다면 해당 보석은 굳이 구매할 필요가 없으므로 왼쪽포인터를 앞으로 한 칸 전진 시켜도 된다.
이런 식으로 왼쪽포인터를 더 이상 이동시킬 수 없을 때까지 최대한 이동시킨 뒤에, 최종적으로 정답으로 왼쪽 포인터와 오른쪽 포인터 위치를 리턴해주면 된다.
시간복잡도
오른쪽 포인터가 최대 100,000번 이동할 수 있고, 왼쪽 포인터도 최대 100,000번 이동할 수 있으므로 총 200,000 번의 함수 반복이 예상된다.
워낙 적은 연산 횟수라 시간 초과는 딱히 신경 쓸 것 없다.
코드
#include <string>
#include <vector>
#include <iostream>
#include <map>
using namespace std;
vector<int> solution(vector<string> gems) {
vector<int> answer(2);
map<string,int> m;
int left_p = 0, right_p = 0;
while(right_p < gems.size()) {
//새로운 보석 발견했을 경우
if(m.find(gems[right_p]) == m.end()) {
m[gems[right_p]] = 1;
answer[0] = left_p; answer[1] = right_p;
right_p++;
continue;
}
//오른쪽 포인터로 발견한 보석 갱신
m[gems[right_p]] = m[gems[right_p]] + 1;
// 왼쪽 포인터를 한칸 늘려줘야하는 경우
if(gems[left_p] == gems[right_p]){
while(m[gems[left_p]] != 1) {
m[gems[left_p]] = m[gems[left_p]] - 1;
left_p++;
}
int answer_gap = answer[1] - answer[0];
int current_gap = right_p - left_p;
if(current_gap < answer_gap) {
answer[0] = left_p; answer[1] = right_p;
}
}
right_p++;
}
answer[0] = answer[0] + 1;
answer[1] = answer[1] + 1;
return answer;
}
int main() {
vector<int> result;
//Test Input
result = solution(vector<string>{"DIA","DIA","EE","EE","OK","DIA"});
cout << result[0] << " " << result[1] << endl;
return 0;
}