프로그래머스 - 보석 쇼핑 [C++]

 이 문제는 투 포인터와 맵을 이용해서 풀었다. gems 배열의 최대 크기가 100,000 이므로 O(n) 시간 이내의 알고리즘을 구상해야 한다. 구간에 대한 정답을 도출해야 하므로 투 포인터를 떠올렸고, 개수에 상관없이 종류가 모두 들어가야하므로 맵을 떠올렸다.

 

 

 일단 투 포인터를 사용하는 방식에는 한쪽에서 모두 시작하는 것과 양쪽에서 서로 시작하는 것이 있는데, 최소 구간이 같을 경우 시작 진열대 번호가 같아야하므로 왼쪽에서 모두 시작하는 쪽이 더 직관적이라고 생각했다. 처음에는 구간을 찾고 모든 보석의 종류가 들어있는지를 확인하기 위해 mp을 순회하면서 개수를 세는 쪽으로 하려 했으나, 이 방식은 시간 초과가 날 것이다. 만약 입력 배열이 10만이고 각 원소가 모두 다른 보석이라면, 10만 * 10만의 연산을 하기 때문이다.

 그래서 두번째 방식으로 mp의 size를 통해 계산하는 방법을 생각했다. 이를 위해서는 left가 옮겨갈 때 mp의 카운트가 0이 되면 그 요소를 맵에서 제거해줘야 한다. 맵의 find 연산과 erase 연산이 O(log n) 시간만 되어준다면 시간 초과가 나지 않을 것이라 생각했고, 실제로 시간 초과가 나지 않고 정답을 도출할 수 있었다.

 

 

#include <string>
#include <vector>
#include <map>
#include <algorithm>

using namespace std;

vector<int> solution(vector<string> gems) {
    vector<int> answer;
    
    map<string, int> tempCnt;
    
    for (string& gem : gems) {
        tempCnt[gem]++;
    }
    
    int allSize = tempCnt.size();
    int size = gems.size();
    
    map<string, int> mp;
    
    int left = 0;
    int right = 0;
    mp[gems[left]]++;
    int answerLeft = 0;
    int answerRight = size;
    
    while (left <= right && right < size) {
        if (allSize == mp.size()) { // 만족하는 경우
            int range = right - left + 1;
            
            if (range < answerRight - answerLeft + 1) {
                answerLeft = left;
                answerRight = right;
            }
            else if (range == answerRight - answerLeft + 1) {
                answerLeft = min(answerLeft, left);
                answerRight = min(answerRight, right);
            }
            
            mp[gems[left]]--;
            if (mp[gems[left]] == 0) {
                auto it = mp.find(gems[left]);
                mp.erase(it);
            }
            left++;
            
            continue;
        }
        
        // 만족하지 않는 경우
        right++;
        if (right < size) {
            mp[gems[right]]++;
        }
    }
    
    answer.push_back(answerLeft + 1);
    answer.push_back(answerRight + 1);
    
    return answer;
}