투포인터의 특징

• left와 right의 증감조건을 생각해보자.
• left를 for문 돌리고 , right는 와일문인데, right < size() 까지만
  진행해야 한다.

  right부터 계속 증가시킨다. 조건에 만족할때 까지
  그 후에 left를 하나씩 증가시킨다.
  이 조건으로 코드를 작성하면
  for(left < size(); left++)
  {
  while(right < size())
  {
  right++;
  }
  }

놓친 부분!

• right 증가할때 조건문 처리해야한다.
  
  -> 사각형 부분 처리를 해야 투포인터 조건이 성립한다.

• 동일한 길이이면 가장 앞선거 선택하는 부분에 대한 고찰
  
  -> 분홍 친 부분을 왜 해야 하냐면
  

left = 1이고 right = 7부터 갱신이 된다.
우리가 찾고자 하는거는 가장 짧은 길이일때를 구하는 것이므로 등호를 사용하지 않은 상태에서 진행한다. 등호를 사용한다면 이외의 값들이 출력될 수 있다.

• 그리고 왜 size() + 1이 냐면
  

: 이 때 +1을 하지 않으면 max는 5이다.

-> 조건문 안에 들어가지도 못하게 되는 문제가 생긴다.

풀이전략

1) 투포인터를 알아야한다.
2) 나동빈 이코테 : 특정한 합을 가지는 부분 연속 수열 찾기 (투 포인터) 공부
3) set과, map에서의 erase를 어떻게 사용할 것이냐?가 관건

map.erase("key")

: 하면 아예 키와 value값이 사라진다.

소스코드

#include <string>
#include <vector>
#include <set>
#include <unordered_map>
using namespace std;

vector<int> solution(vector<string> gems) {
	vector<int> answer;

	set<string>s(gems.begin(), gems.end());

	int right = 0;

	unordered_map<string, int>m;
	int minLeft = 0;
	int minRight = 0;

	int min = 100000;

	for (int left = 0; left < gems.size(); left++)
	{
		while (right < gems.size() && m.size() != s.size())
		{
			m[gems[right]]++;
			right++;
		}

		if (m.size() == s.size())
		{
			

			int tmp = right - left;
			
			if (tmp < min)
			{
				min = tmp;
				minLeft = left;
				minRight = right;
			}
				
		}

			
		m[gems[left]]--;

		if (m[gems[left]] == 0)
		{
			m.erase(gems[left]);
		}
		//answer.push_back()
		//break;
	}

	answer.push_back(minLeft + 1);
	answer.push_back(minRight);
	return answer;
}

int main() {

	//vector<string>v = { "DIA", "RUBY", "RUBY", "DIA", "DIA", "EMERALD", "SAPPHIRE", "DIA" };
	//vector<string>v = { "AA", "AB", "AC", "AA", "AC" };
	//vector<string>v = { "XYZ", "XYZ", "XYZ" };
	vector<string>v = { "ZZZ", "YYY", "NNNN", "YYY", "BBB" };
	solution(v);
	return 0;

}

두번째 풀이

#include <string>
#include <vector>
#include <set>
#include <map>
using namespace std;
 
//적어도 모든 종류의 보석을 구매해야 한다.  => set을 사용하자. 
//무조건 연속적이어야 한다. => 투포인터를 사용하자. 
//시작 번호와 끝 번호를 알고 있어야 한다. 변수 2개 필요하다. 
//짧은구간이 여러개면 시작 진열 번호 가장 작은 친구를 리턴
//mapping으로 보석 ++ 하다가 0이 되면 erase를하자. 

vector<int> solution(vector<string> gems) {
    vector<int> answer;
   
    set<string>s;
    for(const auto i : gems)
        s.insert(i);
    
    map<string,int>m;
    
    int right = 0;
    int left = 0;
    
    int max = gems.size() + 1;
    
    int resultR = 0;
    int resultL = 0;
    for(left = 0; left < gems.size(); left++)
    {
        while(right < gems.size() && s.size() != m.size())
        {
            m[gems[right]]++;
            right++;
            
        }
       
        if(m.size() == s.size())
        {
            if(max > right - left)
            {
                max = right - left;  
                resultR = right;
                resultL = left;
            }
           
        }
        m[gems[left]]--;
        
        if(m[gems[left]] == 0)
        {
            m.erase(gems[left]);          
        }
            
        
    }
    answer.push_back(resultL + 1);
    answer.push_back(resultR);
    
    
    return answer;
}