[프로그래머스] 보석 쇼핑 (2020 카카오 인턴십)

문제 링크 : programmers.co.kr/learn/courses/30/lessons/67258

 

 

이번 문제는 투포인터 문제다. 그냥 단순하게 모든 경우의 수 확인한다면 O(n^2)이 나올것이다. 

하지만 투포인터를 이용하면 O(n)으로 해결할 수 있다.

 

 

<전체적인 알고리즘>

1. 보석을 set에 넣어서 보석 종류의 개수를 확인한다.

2. 투포인터(start , end)를 이용하여 증가시키며 확인한다.   

        2-1 투포인터 범위안에 보석종류가 포함안된게 있거나 start==end라면 end증가시켜 범위 늘리기   

        2-2 투포인터 범위안에 보석종류가 전부 포함되면 start 증가시키며 범위 축소해보기

3. 확인한 범위 중 최소의 범위 반환

 

<전체 코드>

#include<iostream>
#include <string>
#include <vector>
#include<set>
#include<map>

using namespace std;

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

    set<string> s;
    map<string,int> m;
    map<string,int>::iterator iter;
    
	for (int i = 0; i < gems.size(); i++)
	{
		s.insert(gems[i]);   //보석종류 개수 알아보기
	}

	vector<int> answer{ 1,1 };
	int start = 0;
	int end = 0;
	int minn = 987654321;
	m.insert(make_pair(gems[0], 1));  // 처음 보석 삽입
	if (m.size() == s.size())minn = 0;  //보석 종류가 하나면 끝

	while (1)
	{
		if (start == end || m.size() != s.size())  //투포인터 index가 같거나 포함안된 보석종류 있으면 
		{                                             
			end++;                
			if (end > gems.size() - 1)break;
			m[gems[end]]++;       //보석 삽입
		}
		else    //보석 종류가 다 포함되면 
		{
			if (end - start < minn)   //지금까지 나온 범위중에 최소이면 index저장
			{
				minn = end - start;
				answer[0] = start + 1;
				answer[1] = end + 1;
			}
			iter = m.find(gems[start]);
			iter->second--;           //start포인터 이동시켜야 하니 그전 start보석 빼주기
			if (iter->second == 0)m.erase(iter);  //해당 보석이 0개가되면 보석종류 없애기
			start++;
		}
	}
	return answer;
}

 

 

궁금하신 점은 댓글에 남겨주시면 답변드리겠습니다.