보석 쇼핑 [카카오 2020 인턴 코딩테스트] C++ 투포인터 간단 명확 풀이

전형적인 투포인터 문제이다.

 

 

 

다음과 같이

for(int i=0;i<gems.size();i++)
    s.insert(gems[i]);

 

set을 이용해 중복되지않은 보석의 개수를 구했고

 

while문을 돌며 투포인터 lo , hi를 증가시켜가며 Map에다 현재 start와 end를 저장했다.

 

 

- map으로 투포인터의 범위를 저장한 이유 

 

처음엔 map대신 set을 사용했으나 투포인터에서 지나간 범위는 삭제를 해줘야하는데

 

만약 set으로 해놓고 DIA를 지워버리면 범위내에 또 DIA가 있다면 지워지지 않아야할 원소도 지우기 때문이다.

 

따라서 Map을 사용하여 (Map <String,int>) 보석의 이름과 그 보석이 마지막으로 위치했던 인덱스를 저장해놓는다.

 

이렇게 저장해놓는다면 DIA가 0과 3 두군데에 있엇다면 0에있는 DIA를 지나갈때는 지우지 않고 3에있는 DIA를 지나갈때만 Map에서 삭제한다.

 

if(m[gems[lo]]==lo)
  m.erase(gems[lo]); 

 

다음 그림과 같이, Map 사이즈가 Set사이즈와 동일해 진다면 정답범위를 나타내는 벡터 v에 저장하고

Map에서 삭제해야 하는 보석이면 삭제하고 lo를 증가시켜 투포인터를 계속 순회한다.

	if(m.size()==s.size())
        {
            v.push_back(make_pair(lo,hi-1));
            
            if(m[gems[lo]]==lo)
                m.erase(gems[lo]);  
            lo++;
            
            if(hi>gems.size()) break;
        }

 

 

배열의 범위가 최대 10만 이므로 브루트 포스방식으로 푼다면 O(n^2)이 된다. 이는 정확성 풀이에서는 다 맞출 수 있지만

 

효율성 풀이에서 통과할 수 없다. 따라서 투포인터 방식으로 다음과 같이 풀어야 한다.

 

 

 

정답 코드 

 

#include <string>
#include <vector>
#include <set>
#include <map>
#include <algorithm>
#include <iostream>
using namespace std;

bool comp(pair <int,int> a,pair <int,int> b)
{
    if(a.second-a.first == b.second-b.first)
        return a.first<b.first;
    return a.second-a.first < b.second-b.first;
}

vector<int> solution(vector<string> gems) {
    vector<int> answer;
    
    set <string> s;
    map <string,int> m;
    
    for(int i=0;i<gems.size();i++)
    s.insert(gems[i]);
    
    vector <pair <int,int> > v;
    int lo=0; int hi=0;
    
    while(true)
    {
        if(m.size()==s.size())
        {
            v.push_back(make_pair(lo,hi-1));
            
            if(m[gems[lo]]==lo)
                m.erase(gems[lo]);  
            lo++;
            
            if(hi>gems.size()) break;
        }
        else
        {
            if(hi>=gems.size()) break;
            
            m[gems[hi]]=hi;
            hi++;
        }
        
        
    }
    
    sort(v.begin(),v.end(),comp);
    answer.push_back(v[0].first+1);
    answer.push_back(v[0].second+1);
    return answer;
}