[프로그래머스] 보석 쇼핑 (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. 확인한 범위 중 최소의 범위 반환

 

<전체 코드>

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50

#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; }

 

 

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