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

 

 

문제

문제 설명

 

 

 

풀이

 

[문제 요약]

 

이 문제는 연속 된 구간을 선택하고 모든 종류의 보석을 전부 구매할 수 있는지를 계산하는 문제다.

 

구간을 2중 for문으로 탐색할 경우 O(N^2) 이지만, 누적 합과 비슷하게 특정 자리의 보석이 빠지거나 들어올 때, 그 보석의 개수를 고려하면 쉽게 풀 수 있는 문제다.

 

먼저 모든 종류의 보석의 수를 구한다. 그리고 구간의 시작지점 st와 끝나는 지점 ed를 정한다.

이후 처음 보석부터 모든 종류의 보석이 모일때까지의 구간을 구한다.

 

이제 모든 종류의 보석이 모였다면 st를 한 칸씩 앞으로 당기면서 보석을 뺀다.

 

만 보석을 뺐는데 그 보석의 수가 0이라면, 모든 보석을 구매할 수 없는 경우이므로, 구간의 끝인 ed를 늘리고 구간에 새 보석을 넣는다.

새 보석을 넣어도 빠진 보석의 수가 아직 0이라면 계속 ed를 늘리며 보석의 수가 1이 될 때 까지 반복한다.

(이 보석의 수가 1이 되어야 모든 보석을 모은 경우다.)

다시 보석의 수가 1이 된다면 st을 한 칸씩 당겨 보석을 빼고 보석의 수를 센다.

 

즉 아래 그림과 같이 진행 된다.

이렇게 문제를 풀 경우 O(N)으로 해결할 수 있다. 

 

쉽게 생각해 한쪽은 보석을 넣기만하고 한쪽은 보석을 빼기만 한다.

이 때 보석이 빠져 개수가 0이 된다면 한쪽에서는 보석을 순서대로 넣으면서, 빠진 보석의 개수가 1이 되는지 검사하면 된다.

 

 

[아이디어 정리]

1. 보석의 종류를 전부 구한다.​
2. 구간의 처음(st)부터 시작해 모든 보석이 포함될 때 까지 구간의 끝(ed)을 늘린다.
3. 모든 보석이 포함 되었다면, 시작하는 구간을 줄이면서 구간의 길이를 비교하고, 보석의 수가 0이 되는지 탐색한다.
4. 보석의 수가 0이 된다면 그 보석을 채워야 모든 보석이 포함되므로 ed 구간을 늘려 보석의 수가 다시 1이 될 때 까지 탐색한다.

 

 

Code

 

 

#include <string>
#include <vector>
#include <map>
using namespace std;

bool find(vector<pair<string,int>>&gemV, int &idx) //idx는 비교할 보석의 idx
{
    if (idx==-1)
    {
        for (int i=0; i<gemV.size(); i++)
        {
            if (gemV[i].second==0)
            {
                return false;
            }
        }
        return true;
    }
    else
    {
        if (gemV[idx].second==0)
            return false;
    }
    return true;
    
}

vector<int> solution(vector<string> gems) {
    vector<int> answer(2);
    map<string,int> gemMap,gemDict;
    for (int i=0; i<gems.size(); i++)
    {
        gemMap[gems[i]]=0;        
    }
    vector<pair<string,int>> gemV(gemMap.begin(),gemMap.end());
    for (int i=0; i<gemV.size(); i++)
    {
        gemDict[gemV[i].first]=i;
    }
    int ed=0,st=0;
    gemV[gemDict[gems[0]]].second=1;
    int minSize=gems.size(), idx=-1;
    while(st<gems.size())
    {
        if (find(gemV,idx))
        {
            if (ed-st<minSize)
            {
                answer[0]=st+1,answer[1]=ed+1;
                minSize=ed-st;
            }
            gemV[gemDict[gems[st]]].second-=1;
            idx = gemDict[gems[st]];
            st++;
        }
        else
        {
            if (ed<gems.size()-1)
            {
                ed++;
                gemV[gemDict[gems[ed]]].second+=1;                
            }
            else
            {
                st++;
            }
        }
    }
    return answer;
}

 

---

 

처음에 모든 보석이 포함되었는지를 for문으로 검사해서 효율성 테스트에서 실패했다.

이후 빠진 보석만 검사하도록 코드를 바꿨는데, 이 과정에서 코드가 길어졌다;;

그냥 size()로 모든 보석이 포함되었는지 검사하면 빠르고 코드도 깔끔했을텐데... 

 

프로그래머스