[1일 1알고] 보석 쇼핑

https://school.programmers.co.kr/learn/courses/30/lessons/67258

프로그래머스

 

문제를 읽자마자 투포인터로 풀어야한다는 느낌이 듭니다.

 

다만 이런 문제는 구현할 때 실수가 생기기 쉽죠 

물론 제가 실수해서 하는 말입니다.

---

아이디어는 간단합니다. 투포인터로 left, right 인덱스를 관리하며 모두 포함한다면 left를, 포함하고 있지 않다면 right를 움직이는 방식으로 계산해나가면 됩니다.

 

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

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

    unordered_map<string, int> gemMap;

    for (auto gem : gems)
    {
        if (gemMap.find(gem) == gemMap.end())
        {
            gemMap.insert({ gem, 0 });
        }
        else
        {
            ++gemMap[gem];
        }
    }

    int l = 0, r = 0;
    int N = gems.size();
    int kind = gemMap.size();
    vector<int> answer;
    answer = { 1, N };
    int ansLen = N;

    unordered_map<string, int> gemCnt;

    for (auto [gem, cnt] : gemMap)
    {
        gemCnt.insert({ gem, 0 });
    }

    unordered_set<string> gemSet;
    while (l < N && r < N)
    {
        int size = gemSet.size();
        if (size == kind)
        {
            --gemCnt[gems[l]];
            if (gemCnt[gems[l]] == 0)
            {
                gemSet.erase(gems[l]);
            }

            if (ansLen > r - l)
            {
                answer = { l+1, r};
                ansLen = r - l;
            }

            ++l;
        }
        else
        {
            ++gemCnt[gems[r]];
            if (gemCnt[gems[r]] == 1)
            {
                gemSet.insert(gems[r]);
            }
            ++r;
        }
    }

    while (l < N && gemSet.size() == kind)
    {
        if (ansLen > r - l)
        {
            answer = { l + 1, r };
            ansLen = r - l;
        }

        --gemCnt[gems[l]];

        if (gemCnt[gems[l]] == 0)
        {
            gemSet.erase(gems[l]);
        }

        ++l;
    }

    return answer;
}

 

코드에 부족한 점이 많네요