[Algorithm] Programmers :: 보석 쇼핑

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

프로그래머스

unordered_map<string, int> check;
 
vector<int> solution(vector<string> gems) 
{
    int minLeft = 0;
    int minRight = 0x3f3f3f3f;
    int targetCount = 0;
 
    for (int i = 0; i < gems.size(); ++i)
    {
        check[gems[i]]++;
    }
 
    targetCount = check.size();
    int start = 0;
    int end = 0;
    int count = 0;
    bool isUpdate = true;
    check.clear();
 
    while (end < gems.size())
    {
        if (isUpdate)
        {
            if (check[gems[end]] == 0) ++count;
            ++check[gems[end]];
        }
        else isUpdate = true;
 
        if (count == targetCount)
        {
            if (end - start < minRight - minLeft)
            {
                minLeft = start;
                minRight = end;
            }
 
            if (minRight - minLeft + 1 == targetCount) break;
 
            ++start;
            --check[gems[start-1]];
 
            if (check[gems[start - 1]] == 0) --count;
            else
            {
                isUpdate = false;
                continue;
            }
        }
 
        ++end;
    }
 
    return { minLeft + 1,minRight + 1 };
}

gems의 크기는 100,000이기 때문에 N^2의 완전탐색으로는 당연히 안되고, 투포인터로 해결해야하는 문제입니다.

먼저 총 몇개의 서로다른 보석을 구해야하는지(targetCount) 알아냅니다.

그러기 위해서 gems 순회를하면서 ++을 해줬고, 그렇게 알아낸 check.size()를 targetCount로 잡습니다.

이후의 로직을 위해 check는 clear해줍니다.

 

이후 left, right를 0으로 맞춰놓고 로직을 수행합니다.

반복문의 맨 첫부분에서 end에 해당하는 부분에 대해 카운팅을 먼저 해줍니다. 해당 값이 0, 즉 아예 새로운 보석을 찾았다면 ++count를 해줍니다. 그리고 새로운 보석여부와 상관없이 맵에 ++을 해줍니다.

 

현재 범위내에 각각의 보석을 몇개씩 갖고 있는지를 계속 알고 있어야 합니다.

이후, count값이 targetCount와 같다면 일단 답 갱신을 해줍니다. 만약 targetCount와 범위의 크기가 동일하다면 이후 로직을 수행할 필요 없이 바로 return 시킵니다. (범위가 더 좁혀질 수 없기 때문)

 

값 갱신 이후, 새로운 경우의수를 찾아야하기 때문에 start를 한칸 올려줍니다. 여기서 한칸올리기 전인 기존의 start에 해당하는 부분에 대해서는 맵에서 --를 해줍니다. 

이 때, --를 했는데 해당 값이 아예 0이 되버린다면, count값도 --를 해줍니다. 범위내에 해당보석이 아예 없기 때문입니다.

만약 --를 했는데도(start를 한칸 올렸는데도) 여전히 범위내에 동일한 종류의 보석이 있다면 isUpdate라는 bool값을 false로 변경해주고 바로 continue합니다.

바로 continue하는 이유는 반복문의 가장 아래에 있는 end값을 한칸 올리는것을 안하기 위해서입니다.

 

왜냐하면 start를 한칸 올렸는데도 여전히 count값이 동일, 즉 targetCount값을 유지하고 있다면 다음 반복문로직때 end는 그대로인 상태에서 값을 갱신시켜줘야하기 때문입니다.

이 부분에 대해서는 그냥 start를 올렸을 때 여전히 targetCount값을 유지하고 있다면, 해당부분에서 또 while문 돌려서 start를 쭉 땡겨버려도 됩니다. 실제로 다른분들의 코드같은 경우 그렇게 하는 경우도 많습니다.

 

프로그래머스 3레벨급 투포인터는 처음풀어봤는데, 풀어보길 잘했다는 생각이 듭니다.

처음에는 개수를 저장안하고 그냥 true, false로만 체크하다가 풀리지도 않고 코드에 조건문들이 많아져서 문제를 해결하지 못했는데, 다른 분들이 올려주신 테스트케이스를 대입하다보니 개수를 카운팅해야한다는것을 알고 해결할 수 있었습니다.

 

문제에 있는 케이스 외의 테스트케이스입니다. 우측의 주석부분이 정답입니다.

 

 { "A", "A", "A", "B", "B" };  // 3,4
 { "A" };  // 1, 1
 { "A", "B", "B", "B", "B", "B", "B", "C", "B", "A" };  // 8, 10
 { "A", "B", "C", "B", "F", "D", "A", "F", "B", "D", "B" }; // [3, 7] 
 { "A", "B", "B", "C", "A", "B", "C", "A", "B", "C" }; // [3, 5] 
 { "DIA", "EM", "EM", "RUB", "DIA"}; // [3, 5] 
 { "A", "AA", "AA", "AAA", "AA", "A" }; // [4,6]